src/ceph/src/os/bluestore/bluestore_types.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * Ceph - scalable distributed file system
   5  *
   6  * Copyright (C) 2014 Red Hat
   7  *
   8  * This is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License version 2.1, as published by the Free Software
  11  * Foundation.  See file COPYING.
  12  *
  13  */
  14
  15 #ifndef CEPH_OSD_BLUESTORE_BLUESTORE_TYPES_H
  16 #define CEPH_OSD_BLUESTORE_BLUESTORE_TYPES_H
  17
  18 #include <ostream>
  19 #include <bitset>
  20 #include "include/types.h"
  21 #include "include/interval_set.h"
  22 #include "include/utime.h"
  23 #include "common/hobject.h"
  24 #include "compressor/Compressor.h"
  25 #include "common/Checksummer.h"
  26 #include "include/mempool.h"
  27
  28 namespace ceph {
  29   class Formatter;
  30 }
  31
  32 /// label for block device
  33 struct bluestore_bdev_label_t {
  34   uuid_d osd_uuid;     ///< osd uuid
  35   uint64_t size;       ///< device size
  36   utime_t btime;       ///< birth time
  37   string description;  ///< device description
  38
  39   map<string,string> meta; ///< {read,write}_meta() content from ObjectStore
  40
  41   void encode(bufferlist& bl) const;
  42   void decode(bufferlist::iterator& p);
  43   void dump(Formatter *f) const;
  44   static void generate_test_instances(list<bluestore_bdev_label_t*>& o);
  45 };
  46 WRITE_CLASS_ENCODER(bluestore_bdev_label_t)
  47
  48 ostream& operator<<(ostream& out, const bluestore_bdev_label_t& l);
  49
  50 /// collection metadata
  51 struct bluestore_cnode_t {
  52   uint32_t bits;   ///< how many bits of coll pgid are significant
  53
  54   explicit bluestore_cnode_t(int b=0) : bits(b) {}
  55
  56   DENC(bluestore_cnode_t, v, p) {
  57     DENC_START(1, 1, p);
  58     denc(v.bits, p);
  59     DENC_FINISH(p);
  60   }
  61   void dump(Formatter *f) const;
  62   static void generate_test_instances(list<bluestore_cnode_t*>& o);
  63 };
  64 WRITE_CLASS_DENC(bluestore_cnode_t)
  65
  66 class AllocExtent;
  67 typedef mempool::bluestore_alloc::vector<AllocExtent> AllocExtentVector;
  68 class AllocExtent {
  69 public:
  70   uint64_t offset;
  71   uint32_t length;
  72
  73   AllocExtent() {
  74     offset = 0;
  75     length = 0;
  76   }
  77
  78   AllocExtent(int64_t off, int32_t len) : offset(off), length(len) { }
  79   uint64_t end() const {
  80     return offset + length;
  81   }
  82   bool operator==(const AllocExtent& other) const {
  83     return offset == other.offset && length == other.length;
  84   }
  85 };
  86
  87 inline static ostream& operator<<(ostream& out, const AllocExtent& e) {
  88   return out << "0x" << std::hex << e.offset << "~" << e.length << std::dec;
  89 }
  90
  91 class ExtentList {
  92   AllocExtentVector *m_extents;
  93   int64_t m_block_size;
  94   int64_t m_max_blocks;
  95
  96 public:
  97   void init(AllocExtentVector *extents, int64_t block_size,
  98             uint64_t max_alloc_size) {
  99     m_extents = extents;
 100     m_block_size = block_size;
 101     m_max_blocks = max_alloc_size / block_size;
 102     assert(m_extents->empty());
 103   }
 104
 105   ExtentList(AllocExtentVector *extents, int64_t block_size) {
 106     init(extents, block_size, 0);
 107   }
 108
 109   ExtentList(AllocExtentVector *extents, int64_t block_size,
 110              uint64_t max_alloc_size) {
 111     init(extents, block_size, max_alloc_size);
 112   }
 113
 114   void reset() {
 115     m_extents->clear();
 116   }
 117
 118   void add_extents(int64_t start, int64_t count);
 119
 120   AllocExtentVector *get_extents() {
 121     return m_extents;
 122   }
 123
 124   std::pair<int64_t, int64_t> get_nth_extent(int index) {
 125       return std::make_pair
 126             ((*m_extents)[index].offset / m_block_size,
 127              (*m_extents)[index].length / m_block_size);
 128   }
 129
 130   int64_t get_extent_count() {
 131     return m_extents->size();
 132   }
 133 };
 134
 135
 136 /// pextent: physical extent
 137 struct bluestore_pextent_t : public AllocExtent {
 138   const static uint64_t INVALID_OFFSET = ~0ull;
 139
 140   bluestore_pextent_t() : AllocExtent() {}
 141   bluestore_pextent_t(uint64_t o, uint64_t l) : AllocExtent(o, l) {}
 142   bluestore_pextent_t(const AllocExtent &ext) :
 143     AllocExtent(ext.offset, ext.length) { }
 144
 145   bluestore_pextent_t& operator=(const AllocExtent &ext) {
 146     offset = ext.offset;
 147     length = ext.length;
 148     return *this;
 149   }
 150   bool is_valid() const {
 151     return offset != INVALID_OFFSET;
 152   }
 153
 154   DENC(bluestore_pextent_t, v, p) {
 155     denc_lba(v.offset, p);
 156     denc_varint_lowz(v.length, p);
 157   }
 158
 159   void dump(Formatter *f) const;
 160   static void generate_test_instances(list<bluestore_pextent_t*>& ls);
 161 };
 162 WRITE_CLASS_DENC(bluestore_pextent_t)
 163
 164 ostream& operator<<(ostream& out, const bluestore_pextent_t& o);
 165
 166 typedef mempool::bluestore_cache_other::vector<bluestore_pextent_t> PExtentVector;
 167
 168 template<>
 169 struct denc_traits<PExtentVector> {
 170   static constexpr bool supported = true;
 171   static constexpr bool bounded = false;
 172   static constexpr bool featured = false;
 173   static constexpr bool need_contiguous = true;
 174   static void bound_encode(const PExtentVector& v, size_t& p) {
 175     p += sizeof(uint32_t);
 176     const auto size = v.size();
 177     if (size) {
 178       size_t per = 0;
 179       denc(v.front(), per);
 180       p +=  per * size;
 181     }
 182   }
 183   static void encode(const PExtentVector& v,
 184                      bufferlist::contiguous_appender& p) {
 185     denc_varint(v.size(), p);
 186     for (auto& i : v) {
 187       denc(i, p);
 188     }
 189   }
 190   static void decode(PExtentVector& v, bufferptr::iterator& p) {
 191     unsigned num;
 192     denc_varint(num, p);
 193     v.clear();
 194     v.resize(num);
 195     for (unsigned i=0; i<num; ++i) {
 196       denc(v[i], p);
 197     }
 198   }
 199 };
 200
 201
 202 /// extent_map: a map of reference counted extents
 203 struct bluestore_extent_ref_map_t {
 204   struct record_t {
 205     uint32_t length;
 206     uint32_t refs;
 207     record_t(uint32_t l=0, uint32_t r=0) : length(l), refs(r) {}
 208     DENC(bluestore_extent_ref_map_t::record_t, v, p) {
 209       denc_varint_lowz(v.length, p);
 210       denc_varint(v.refs, p);
 211     }
 212   };
 213
 214   typedef mempool::bluestore_cache_other::map<uint64_t,record_t> map_t;
 215   map_t ref_map;
 216
 217   void _check() const;
 218   void _maybe_merge_left(map_t::iterator& p);
 219
 220   void clear() {
 221     ref_map.clear();
 222   }
 223   bool empty() const {
 224     return ref_map.empty();
 225   }
 226
 227   void get(uint64_t offset, uint32_t len);
 228   void put(uint64_t offset, uint32_t len, PExtentVector *release,
 229            bool *maybe_unshared);
 230
 231   bool contains(uint64_t offset, uint32_t len) const;
 232   bool intersects(uint64_t offset, uint32_t len) const;
 233
 234   void bound_encode(size_t& p) const {
 235     denc_varint((uint32_t)0, p);
 236     if (!ref_map.empty()) {
 237       size_t elem_size = 0;
 238       denc_varint_lowz((uint64_t)0, elem_size);
 239       ref_map.begin()->second.bound_encode(elem_size);
 240       p += elem_size * ref_map.size();
 241     }
 242   }
 243   void encode(bufferlist::contiguous_appender& p) const {
 244     uint32_t n = ref_map.size();
 245     denc_varint(n, p);
 246     if (n) {
 247       auto i = ref_map.begin();
 248       denc_varint_lowz(i->first, p);
 249       i->second.encode(p);
 250       int64_t pos = i->first;
 251       while (--n) {
 252         ++i;
 253         denc_varint_lowz((int64_t)i->first - pos, p);
 254         i->second.encode(p);
 255         pos = i->first;
 256       }
 257     }
 258   }
 259   void decode(bufferptr::iterator& p) {
 260     uint32_t n;
 261     denc_varint(n, p);
 262     if (n) {
 263       int64_t pos;
 264       denc_varint_lowz(pos, p);
 265       ref_map[pos].decode(p);
 266       while (--n) {
 267         int64_t delta;
 268         denc_varint_lowz(delta, p);
 269         pos += delta;
 270         ref_map[pos].decode(p);
 271       }
 272     }
 273   }
 274
 275   void dump(Formatter *f) const;
 276   static void generate_test_instances(list<bluestore_extent_ref_map_t*>& o);
 277 };
 278 WRITE_CLASS_DENC(bluestore_extent_ref_map_t)
 279
 280
 281 ostream& operator<<(ostream& out, const bluestore_extent_ref_map_t& rm);
 282 static inline bool operator==(const bluestore_extent_ref_map_t::record_t& l,
 283                               const bluestore_extent_ref_map_t::record_t& r) {
 284   return l.length == r.length && l.refs == r.refs;
 285 }
 286 static inline bool operator==(const bluestore_extent_ref_map_t& l,
 287                               const bluestore_extent_ref_map_t& r) {
 288   return l.ref_map == r.ref_map;
 289 }
 290 static inline bool operator!=(const bluestore_extent_ref_map_t& l,
 291                               const bluestore_extent_ref_map_t& r) {
 292   return !(l == r);
 293 }
 294
 295 /// blob_use_tracker: a set of per-alloc unit ref counters to track blob usage
 296 struct bluestore_blob_use_tracker_t {
 297   // N.B.: There is no need to minimize au_size/num_au
 298   //   as much as possible (e.g. have just a single byte for au_size) since:
 299   //   1) Struct isn't packed hence it's padded. And even if it's packed see 2)
 300   //   2) Mem manager has its own granularity, most probably >= 8 bytes
 301   //
 302   uint32_t au_size; // Allocation (=tracking) unit size,
 303                     // == 0 if uninitialized
 304   uint32_t num_au;  // Amount of allocation units tracked
 305                     // == 0 if single unit or the whole blob is tracked
 306
 307   union {
 308     uint32_t* bytes_per_au;
 309     uint32_t total_bytes;
 310   };
 311
 312   bluestore_blob_use_tracker_t()
 313     : au_size(0), num_au(0), bytes_per_au(nullptr) {
 314   }
 315   ~bluestore_blob_use_tracker_t() {
 316     clear();
 317   }
 318
 319   void clear() {
 320     if (num_au != 0) {
 321       delete[] bytes_per_au;
 322     }
 323     bytes_per_au = 0;
 324     au_size = 0;
 325     num_au = 0;
 326   }
 327
 328   uint32_t get_referenced_bytes() const {
 329     uint32_t total = 0;
 330     if (!num_au) {
 331       total = total_bytes;
 332     } else {
 333       for (size_t i = 0; i < num_au; ++i) {
 334         total += bytes_per_au[i];
 335       }
 336     }
 337     return total;
 338   }
 339   bool is_not_empty() const {
 340     if (!num_au) {
 341       return total_bytes != 0;
 342     } else {
 343       for (size_t i = 0; i < num_au; ++i) {
 344         if (bytes_per_au[i]) {
 345           return true;
 346         }
 347       }
 348     }
 349     return false;
 350   }
 351   bool is_empty() const {
 352     return !is_not_empty();
 353   }
 354   void prune_tail(uint32_t new_len) {
 355     if (num_au) {
 356       new_len = ROUND_UP_TO(new_len, au_size);
 357       uint32_t _num_au = new_len / au_size;
 358       assert(_num_au <= num_au);
 359       if (_num_au) {
 360         num_au = _num_au; // bytes_per_au array is left unmodified
 361
 362       } else {
 363         clear();
 364       }
 365     }
 366   }
 367   void add_tail(uint32_t new_len, uint32_t _au_size) {
 368     auto full_size = au_size * (num_au ? num_au : 1);
 369     assert(new_len >= full_size);
 370     if (new_len == full_size) {
 371       return;
 372     }
 373     if (!num_au) {
 374       uint32_t old_total = total_bytes;
 375       total_bytes = 0;
 376       init(new_len, _au_size);
 377       assert(num_au);
 378       bytes_per_au[0] = old_total;
 379     } else {
 380       assert(_au_size == au_size);
 381       new_len = ROUND_UP_TO(new_len, au_size);
 382       uint32_t _num_au = new_len / au_size;
 383       assert(_num_au >= num_au);
 384       if (_num_au > num_au) {
 385         auto old_bytes = bytes_per_au;
 386         auto old_num_au = num_au;
 387         num_au = _num_au;
 388         allocate();
 389         for (size_t i = 0; i < old_num_au; i++) {
 390           bytes_per_au[i] = old_bytes[i];
 391         }
 392         for (size_t i = old_num_au; i < num_au; i++) {
 393           bytes_per_au[i] = 0;
 394         }
 395         delete[] old_bytes;
 396       }
 397     }
 398   }
 399
 400   void init(
 401     uint32_t full_length,
 402     uint32_t _au_size);
 403
 404   void get(
 405     uint32_t offset,
 406     uint32_t len);
 407
 408   /// put: return true if the blob has no references any more after the call,
 409   /// no release_units is filled for the sake of performance.
 410   /// return false if there are some references to the blob,
 411   /// in this case release_units contains pextents
 412   /// (identified by their offsets relative to the blob start)
 413   ///  that are not used any more and can be safely deallocated.
 414   bool put(
 415     uint32_t offset,
 416     uint32_t len,
 417     PExtentVector *release);
 418
 419   bool can_split() const;
 420   bool can_split_at(uint32_t blob_offset) const;
 421   void split(
 422     uint32_t blob_offset,
 423     bluestore_blob_use_tracker_t* r);
 424
 425   bool equal(
 426     const bluestore_blob_use_tracker_t& other) const;
 427
 428   void bound_encode(size_t& p) const {
 429     denc_varint(au_size, p);
 430     if (au_size) {
 431       denc_varint(num_au, p);
 432       if (!num_au) {
 433         denc_varint(total_bytes, p);
 434       } else {
 435         size_t elem_size = 0;
 436         denc_varint((uint32_t)0, elem_size);
 437         p += elem_size * num_au;
 438       }
 439     }
 440   }
 441   void encode(bufferlist::contiguous_appender& p) const {
 442     denc_varint(au_size, p);
 443     if (au_size) {
 444       denc_varint(num_au, p);
 445       if (!num_au) {
 446         denc_varint(total_bytes, p);
 447       } else {
 448         size_t elem_size = 0;
 449         denc_varint((uint32_t)0, elem_size);
 450         for (size_t i = 0; i < num_au; ++i) {
 451           denc_varint(bytes_per_au[i], p);
 452         }
 453       }
 454     }
 455   }
 456   void decode(bufferptr::iterator& p) {
 457     clear();
 458     denc_varint(au_size, p);
 459     if (au_size) {
 460       denc_varint(num_au, p);
 461       if (!num_au) {
 462         denc_varint(total_bytes, p);
 463       } else {
 464         allocate();
 465         for (size_t i = 0; i < num_au; ++i) {
 466           denc_varint(bytes_per_au[i], p);
 467         }
 468       }
 469     }
 470   }
 471
 472   void dump(Formatter *f) const;
 473   static void generate_test_instances(list<bluestore_blob_use_tracker_t*>& o);
 474 private:
 475   void allocate();
 476 };
 477 WRITE_CLASS_DENC(bluestore_blob_use_tracker_t)
 478 ostream& operator<<(ostream& out, const bluestore_blob_use_tracker_t& rm);
 479
 480 /// blob: a piece of data on disk
 481 struct bluestore_blob_t {
 482 private:
 483   PExtentVector extents;              ///< raw data position on device
 484   uint32_t logical_length = 0;        ///< original length of data stored in the blob
 485   uint32_t compressed_length = 0;     ///< compressed length if any
 486
 487 public:
 488   enum {
 489     LEGACY_FLAG_MUTABLE = 1,  ///< [legacy] blob can be overwritten or split
 490     FLAG_COMPRESSED = 2,      ///< blob is compressed
 491     FLAG_CSUM = 4,            ///< blob has checksums
 492     FLAG_HAS_UNUSED = 8,      ///< blob has unused map
 493     FLAG_SHARED = 16,         ///< blob is shared; see external SharedBlob
 494   };
 495   static string get_flags_string(unsigned flags);
 496
 497   uint32_t flags = 0;                 ///< FLAG_*
 498
 499   typedef uint16_t unused_t;
 500   unused_t unused = 0;     ///< portion that has never been written to (bitmap)
 501
 502   uint8_t csum_type = Checksummer::CSUM_NONE;      ///< CSUM_*
 503   uint8_t csum_chunk_order = 0;       ///< csum block size is 1<<block_order bytes
 504
 505   bufferptr csum_data;                ///< opaque vector of csum data
 506
 507   bluestore_blob_t(uint32_t f = 0) : flags(f) {}
 508
 509   const PExtentVector& get_extents() const {
 510     return extents;
 511   }
 512
 513   DENC_HELPERS;
 514   void bound_encode(size_t& p, uint64_t struct_v) const {
 515     assert(struct_v == 1 || struct_v == 2);
 516     denc(extents, p);
 517     denc_varint(flags, p);
 518     denc_varint_lowz(logical_length, p);
 519     denc_varint_lowz(compressed_length, p);
 520     denc(csum_type, p);
 521     denc(csum_chunk_order, p);
 522     denc_varint(csum_data.length(), p);
 523     p += csum_data.length();
 524     p += sizeof(unused_t);
 525   }
 526
 527   void encode(bufferlist::contiguous_appender& p, uint64_t struct_v) const {
 528     assert(struct_v == 1 || struct_v == 2);
 529     denc(extents, p);
 530     denc_varint(flags, p);
 531     if (is_compressed()) {
 532       denc_varint_lowz(logical_length, p);
 533       denc_varint_lowz(compressed_length, p);
 534     }
 535     if (has_csum()) {
 536       denc(csum_type, p);
 537       denc(csum_chunk_order, p);
 538       denc_varint(csum_data.length(), p);
 539       memcpy(p.get_pos_add(csum_data.length()), csum_data.c_str(),
 540              csum_data.length());
 541     }
 542     if (has_unused()) {
 543       denc(unused, p);
 544     }
 545   }
 546
 547   void decode(bufferptr::iterator& p, uint64_t struct_v) {
 548     assert(struct_v == 1 || struct_v == 2);
 549     denc(extents, p);
 550     denc_varint(flags, p);
 551     if (is_compressed()) {
 552       denc_varint_lowz(logical_length, p);
 553       denc_varint_lowz(compressed_length, p);
 554     } else {
 555       logical_length = get_ondisk_length();
 556     }
 557     if (has_csum()) {
 558       denc(csum_type, p);
 559       denc(csum_chunk_order, p);
 560       int len;
 561       denc_varint(len, p);
 562       csum_data = p.get_ptr(len);
 563       csum_data.reassign_to_mempool(mempool::mempool_bluestore_cache_other);
 564     }
 565     if (has_unused()) {
 566       denc(unused, p);
 567     }
 568   }
 569
 570   bool can_split() const {
 571     return
 572       !has_flag(FLAG_SHARED) &&
 573       !has_flag(FLAG_COMPRESSED) &&
 574       !has_flag(FLAG_HAS_UNUSED);     // splitting unused set is complex
 575   }
 576   bool can_split_at(uint32_t blob_offset) const {
 577     return !has_csum() || blob_offset % get_csum_chunk_size() == 0;
 578   }
 579
 580   void dump(Formatter *f) const;
 581   static void generate_test_instances(list<bluestore_blob_t*>& ls);
 582
 583   bool has_flag(unsigned f) const {
 584     return flags & f;
 585   }
 586   void set_flag(unsigned f) {
 587     flags |= f;
 588   }
 589   void clear_flag(unsigned f) {
 590     flags &= ~f;
 591   }
 592   string get_flags_string() const {
 593     return get_flags_string(flags);
 594   }
 595
 596   void set_compressed(uint64_t clen_orig, uint64_t clen) {
 597     set_flag(FLAG_COMPRESSED);
 598     logical_length = clen_orig;
 599     compressed_length = clen;
 600   }
 601   bool is_mutable() const {
 602     return !is_compressed() && !is_shared();
 603   }
 604   bool is_compressed() const {
 605     return has_flag(FLAG_COMPRESSED);
 606   }
 607   bool has_csum() const {
 608     return has_flag(FLAG_CSUM);
 609   }
 610   bool has_unused() const {
 611     return has_flag(FLAG_HAS_UNUSED);
 612   }
 613   bool is_shared() const {
 614     return has_flag(FLAG_SHARED);
 615   }
 616
 617   /// return chunk (i.e. min readable block) size for the blob
 618   uint64_t get_chunk_size(uint64_t dev_block_size) const {
 619     return has_csum() ?
 620       MAX(dev_block_size, get_csum_chunk_size()) : dev_block_size;
 621   }
 622   uint32_t get_csum_chunk_size() const {
 623     return 1 << csum_chunk_order;
 624   }
 625   uint32_t get_compressed_payload_length() const {
 626     return is_compressed() ? compressed_length : 0;
 627   }
 628   uint64_t calc_offset(uint64_t x_off, uint64_t *plen) const {
 629     auto p = extents.begin();
 630     assert(p != extents.end());
 631     while (x_off >= p->length) {
 632       x_off -= p->length;
 633       ++p;
 634       assert(p != extents.end());
 635     }
 636     if (plen)
 637       *plen = p->length - x_off;
 638     return p->offset + x_off;
 639   }
 640
 641   // validate whether or not the status of pextents within the given range
 642   // meets the requirement(allocated or unallocated).
 643   bool _validate_range(uint64_t b_off, uint64_t b_len,
 644                        bool require_allocated) const {
 645     auto p = extents.begin();
 646     assert(p != extents.end());
 647     while (b_off >= p->length) {
 648       b_off -= p->length;
 649       ++p;
 650       assert(p != extents.end());
 651     }
 652     b_len += b_off;
 653     while (b_len) {
 654       assert(p != extents.end());
 655       if (require_allocated != p->is_valid()) {
 656         return false;
 657       }
 658
 659       if (p->length >= b_len) {
 660         return true;
 661       }
 662       b_len -= p->length;
 663       ++p;
 664     }
 665     assert(0 == "we should not get here");
 666   }
 667
 668   /// return true if the entire range is allocated
 669   /// (mapped to extents on disk)
 670   bool is_allocated(uint64_t b_off, uint64_t b_len) const {
 671     return _validate_range(b_off, b_len, true);
 672   }
 673
 674   /// return true if the entire range is unallocated
 675   /// (not mapped to extents on disk)
 676   bool is_unallocated(uint64_t b_off, uint64_t b_len) const {
 677     return _validate_range(b_off, b_len, false);
 678   }
 679
 680   /// return true if the logical range has never been used
 681   bool is_unused(uint64_t offset, uint64_t length) const {
 682     if (!has_unused()) {
 683       return false;
 684     }
 685     uint64_t blob_len = get_logical_length();
 686     assert((blob_len % (sizeof(unused)*8)) == 0);
 687     assert(offset + length <= blob_len);
 688     uint64_t chunk_size = blob_len / (sizeof(unused)*8);
 689     uint64_t start = offset / chunk_size;
 690     uint64_t end = ROUND_UP_TO(offset + length, chunk_size) / chunk_size;
 691     auto i = start;
 692     while (i < end && (unused & (1u << i))) {
 693       i++;
 694     }
 695     return i >= end;
 696   }
 697
 698   /// mark a range that has never been used
 699   void add_unused(uint64_t offset, uint64_t length) {
 700     uint64_t blob_len = get_logical_length();
 701     assert((blob_len % (sizeof(unused)*8)) == 0);
 702     assert(offset + length <= blob_len);
 703     uint64_t chunk_size = blob_len / (sizeof(unused)*8);
 704     uint64_t start = ROUND_UP_TO(offset, chunk_size) / chunk_size;
 705     uint64_t end = (offset + length) / chunk_size;
 706     for (auto i = start; i < end; ++i) {
 707       unused |= (1u << i);
 708     }
 709     if (start != end) {
 710       set_flag(FLAG_HAS_UNUSED);
 711     }
 712   }
 713
 714   /// indicate that a range has (now) been used.
 715   void mark_used(uint64_t offset, uint64_t length) {
 716     if (has_unused()) {
 717       uint64_t blob_len = get_logical_length();
 718       assert((blob_len % (sizeof(unused)*8)) == 0);
 719       assert(offset + length <= blob_len);
 720       uint64_t chunk_size = blob_len / (sizeof(unused)*8);
 721       uint64_t start = offset / chunk_size;
 722       uint64_t end = ROUND_UP_TO(offset + length, chunk_size) / chunk_size;
 723       for (auto i = start; i < end; ++i) {
 724         unused &= ~(1u << i);
 725       }
 726       if (unused == 0) {
 727         clear_flag(FLAG_HAS_UNUSED);
 728       }
 729     }
 730   }
 731
 732   int map(uint64_t x_off, uint64_t x_len,
 733            std::function<int(uint64_t,uint64_t)> f) const {
 734     auto p = extents.begin();
 735     assert(p != extents.end());
 736     while (x_off >= p->length) {
 737       x_off -= p->length;
 738       ++p;
 739       assert(p != extents.end());
 740     }
 741     while (x_len > 0) {
 742       assert(p != extents.end());
 743       uint64_t l = MIN(p->length - x_off, x_len);
 744       int r = f(p->offset + x_off, l);
 745       if (r < 0)
 746         return r;
 747       x_off = 0;
 748       x_len -= l;
 749       ++p;
 750     }
 751     return 0;
 752   }
 753   void map_bl(uint64_t x_off,
 754               bufferlist& bl,
 755               std::function<void(uint64_t,bufferlist&)> f) const {
 756     auto p = extents.begin();
 757     assert(p != extents.end());
 758     while (x_off >= p->length) {
 759       x_off -= p->length;
 760       ++p;
 761       assert(p != extents.end());
 762     }
 763     bufferlist::iterator it = bl.begin();
 764     uint64_t x_len = bl.length();
 765     while (x_len > 0) {
 766       assert(p != extents.end());
 767       uint64_t l = MIN(p->length - x_off, x_len);
 768       bufferlist t;
 769       it.copy(l, t);
 770       f(p->offset + x_off, t);
 771       x_off = 0;
 772       x_len -= l;
 773       ++p;
 774     }
 775   }
 776
 777   uint32_t get_ondisk_length() const {
 778     uint32_t len = 0;
 779     for (auto &p : extents) {
 780       len += p.length;
 781     }
 782     return len;
 783   }
 784
 785   uint32_t get_logical_length() const {
 786     return logical_length;
 787   }
 788   size_t get_csum_value_size() const;
 789
 790   size_t get_csum_count() const {
 791     size_t vs = get_csum_value_size();
 792     if (!vs)
 793       return 0;
 794     return csum_data.length() / vs;
 795   }
 796   uint64_t get_csum_item(unsigned i) const {
 797     size_t cs = get_csum_value_size();
 798     const char *p = csum_data.c_str();
 799     switch (cs) {
 800     case 0:
 801       assert(0 == "no csum data, bad index");
 802     case 1:
 803       return reinterpret_cast<const uint8_t*>(p)[i];
 804     case 2:
 805       return reinterpret_cast<const __le16*>(p)[i];
 806     case 4:
 807       return reinterpret_cast<const __le32*>(p)[i];
 808     case 8:
 809       return reinterpret_cast<const __le64*>(p)[i];
 810     default:
 811       assert(0 == "unrecognized csum word size");
 812     }
 813   }
 814   const char *get_csum_item_ptr(unsigned i) const {
 815     size_t cs = get_csum_value_size();
 816     return csum_data.c_str() + (cs * i);
 817   }
 818   char *get_csum_item_ptr(unsigned i) {
 819     size_t cs = get_csum_value_size();
 820     return csum_data.c_str() + (cs * i);
 821   }
 822
 823   void init_csum(unsigned type, unsigned order, unsigned len) {
 824     flags |= FLAG_CSUM;
 825     csum_type = type;
 826     csum_chunk_order = order;
 827     csum_data = buffer::create(get_csum_value_size() * len / get_csum_chunk_size());
 828     csum_data.zero();
 829     csum_data.reassign_to_mempool(mempool::mempool_bluestore_cache_other);
 830   }
 831
 832   /// calculate csum for the buffer at the given b_off
 833   void calc_csum(uint64_t b_off, const bufferlist& bl);
 834
 835   /// verify csum: return -EOPNOTSUPP for unsupported checksum type;
 836   /// return -1 and valid(nonnegative) b_bad_off for checksum error;
 837   /// return 0 if all is well.
 838   int verify_csum(uint64_t b_off, const bufferlist& bl, int* b_bad_off,
 839                   uint64_t *bad_csum) const;
 840
 841   bool can_prune_tail() const {
 842     return
 843       extents.size() > 1 &&  // if it's all invalid it's not pruning.
 844       !extents.back().is_valid() &&
 845       !has_unused();
 846   }
 847   void prune_tail() {
 848     const auto &p = extents.back();
 849     logical_length -= p.length;
 850     extents.pop_back();
 851     if (has_csum()) {
 852       bufferptr t;
 853       t.swap(csum_data);
 854       csum_data = bufferptr(t.c_str(),
 855                             get_logical_length() / get_csum_chunk_size() *
 856                             get_csum_value_size());
 857     }
 858   }
 859   void add_tail(uint32_t new_len) {
 860     assert(is_mutable());
 861     assert(!has_unused());
 862     assert(new_len > logical_length);
 863     extents.emplace_back(
 864       bluestore_pextent_t(
 865         bluestore_pextent_t::INVALID_OFFSET,
 866         new_len - logical_length));
 867     logical_length = new_len;
 868     if (has_csum()) {
 869       bufferptr t;
 870       t.swap(csum_data);
 871       csum_data = buffer::create(
 872         get_csum_value_size() * logical_length / get_csum_chunk_size());
 873       csum_data.copy_in(0, t.length(), t.c_str());
 874       csum_data.zero(t.length(), csum_data.length() - t.length());
 875     }
 876   }
 877   uint32_t get_release_size(uint32_t min_alloc_size) const {
 878     if (is_compressed()) {
 879       return get_logical_length();
 880     }
 881     uint32_t res = get_csum_chunk_size();
 882     if (!has_csum() || res < min_alloc_size) {
 883       res = min_alloc_size;
 884     }
 885     return res;
 886   }
 887
 888   void split(uint32_t blob_offset, bluestore_blob_t& rb);
 889   void allocated(uint32_t b_off, uint32_t length, const AllocExtentVector& allocs);
 890   void allocated_test(const bluestore_pextent_t& alloc); // intended for UT only
 891
 892   /// updates blob's pextents container and return unused pextents eligible
 893   /// for release.
 894   /// all - indicates that the whole blob to be released.
 895   /// logical - specifies set of logical extents within blob's
 896   /// to be released
 897   /// Returns true if blob has no more valid pextents
 898   bool release_extents(
 899     bool all,
 900     const PExtentVector& logical,
 901     PExtentVector* r);
 902 };
 903 WRITE_CLASS_DENC_FEATURED(bluestore_blob_t)
 904
 905 ostream& operator<<(ostream& out, const bluestore_blob_t& o);
 906
 907
 908 /// shared blob state
 909 struct bluestore_shared_blob_t {
 910   uint64_t sbid;                       ///> shared blob id
 911   bluestore_extent_ref_map_t ref_map;  ///< shared blob extents
 912
 913   bluestore_shared_blob_t(uint64_t _sbid) : sbid(_sbid) {}
 914
 915   DENC(bluestore_shared_blob_t, v, p) {
 916     DENC_START(1, 1, p);
 917     denc(v.ref_map, p);
 918     DENC_FINISH(p);
 919   }
 920
 921
 922   void dump(Formatter *f) const;
 923   static void generate_test_instances(list<bluestore_shared_blob_t*>& ls);
 924
 925   bool empty() const {
 926     return ref_map.empty();
 927   }
 928 };
 929 WRITE_CLASS_DENC(bluestore_shared_blob_t)
 930
 931 ostream& operator<<(ostream& out, const bluestore_shared_blob_t& o);
 932
 933 /// onode: per-object metadata
 934 struct bluestore_onode_t {
 935   uint64_t nid = 0;                    ///< numeric id (locally unique)
 936   uint64_t size = 0;                   ///< object size
 937   map<mempool::bluestore_cache_other::string, bufferptr> attrs;        ///< attrs
 938
 939   struct shard_info {
 940     uint32_t offset = 0;  ///< logical offset for start of shard
 941     uint32_t bytes = 0;   ///< encoded bytes
 942     DENC(shard_info, v, p) {
 943       denc_varint(v.offset, p);
 944       denc_varint(v.bytes, p);
 945     }
 946     void dump(Formatter *f) const;
 947   };
 948   vector<shard_info> extent_map_shards; ///< extent map shards (if any)
 949
 950   uint32_t expected_object_size = 0;
 951   uint32_t expected_write_size = 0;
 952   uint32_t alloc_hint_flags = 0;
 953
 954   uint8_t flags = 0;
 955
 956   enum {
 957     FLAG_OMAP = 1,
 958   };
 959
 960   string get_flags_string() const {
 961     string s;
 962     if (flags & FLAG_OMAP) {
 963       s = "omap";
 964     }
 965     return s;
 966   }
 967
 968   bool has_flag(unsigned f) const {
 969     return flags & f;
 970   }
 971
 972   void set_flag(unsigned f) {
 973     flags |= f;
 974   }
 975
 976   void clear_flag(unsigned f) {
 977     flags &= ~f;
 978   }
 979
 980   bool has_omap() const {
 981     return has_flag(FLAG_OMAP);
 982   }
 983
 984   void set_omap_flag() {
 985     set_flag(FLAG_OMAP);
 986   }
 987
 988   void clear_omap_flag() {
 989     clear_flag(FLAG_OMAP);
 990   }
 991
 992   DENC(bluestore_onode_t, v, p) {
 993     DENC_START(1, 1, p);
 994     denc_varint(v.nid, p);
 995     denc_varint(v.size, p);
 996     denc(v.attrs, p);
 997     denc(v.flags, p);
 998     denc(v.extent_map_shards, p);
 999     denc_varint(v.expected_object_size, p);
1000     denc_varint(v.expected_write_size, p);
1001     denc_varint(v.alloc_hint_flags, p);
1002     DENC_FINISH(p);
1003   }
1004   void dump(Formatter *f) const;
1005   static void generate_test_instances(list<bluestore_onode_t*>& o);
1006 };
1007 WRITE_CLASS_DENC(bluestore_onode_t::shard_info)
1008 WRITE_CLASS_DENC(bluestore_onode_t)
1009
1010 ostream& operator<<(ostream& out, const bluestore_onode_t::shard_info& si);
1011
1012 /// writeahead-logged op
1013 struct bluestore_deferred_op_t {
1014   typedef enum {
1015     OP_WRITE = 1,
1016   } type_t;
1017   __u8 op = 0;
1018
1019   PExtentVector extents;
1020   bufferlist data;
1021
1022   DENC(bluestore_deferred_op_t, v, p) {
1023     DENC_START(1, 1, p);
1024     denc(v.op, p);
1025     denc(v.extents, p);
1026     denc(v.data, p);
1027     DENC_FINISH(p);
1028   }
1029   void dump(Formatter *f) const;
1030   static void generate_test_instances(list<bluestore_deferred_op_t*>& o);
1031 };
1032 WRITE_CLASS_DENC(bluestore_deferred_op_t)
1033
1034
1035 /// writeahead-logged transaction
1036 struct bluestore_deferred_transaction_t {
1037   uint64_t seq = 0;
1038   list<bluestore_deferred_op_t> ops;
1039   interval_set<uint64_t> released;  ///< allocations to release after tx
1040
1041   bluestore_deferred_transaction_t() : seq(0) {}
1042
1043   DENC(bluestore_deferred_transaction_t, v, p) {
1044     DENC_START(1, 1, p);
1045     denc(v.seq, p);
1046     denc(v.ops, p);
1047     denc(v.released, p);
1048     DENC_FINISH(p);
1049   }
1050   void dump(Formatter *f) const;
1051   static void generate_test_instances(list<bluestore_deferred_transaction_t*>& o);
1052 };
1053 WRITE_CLASS_DENC(bluestore_deferred_transaction_t)
1054
1055 struct bluestore_compression_header_t {
1056   uint8_t type = Compressor::COMP_ALG_NONE;
1057   uint32_t length = 0;
1058
1059   bluestore_compression_header_t() {}
1060   bluestore_compression_header_t(uint8_t _type)
1061     : type(_type) {}
1062
1063   DENC(bluestore_compression_header_t, v, p) {
1064     DENC_START(1, 1, p);
1065     denc(v.type, p);
1066     denc(v.length, p);
1067     DENC_FINISH(p);
1068   }
1069   void dump(Formatter *f) const;
1070   static void generate_test_instances(list<bluestore_compression_header_t*>& o);
1071 };
1072 WRITE_CLASS_DENC(bluestore_compression_header_t)
1073
1074
1075 #endif