summaryrefslogtreecommitdiff
path: root/src/os/DBObjectMap.h
blob: 1ff87f1289dcfaa294b40d2fd87760ba627fb912 (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
// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
#ifndef DBOBJECTMAP_DB_H
#define DBOBJECTMAP_DB_H

#include "include/buffer.h"
#include <set>
#include <map>
#include <string>

#include <string>
#include <vector>
#include <tr1/memory>
#include <boost/scoped_ptr.hpp>

#include "ObjectMap.h"
#include "KeyValueDB.h"
#include "osd/osd_types.h"
#include "common/Mutex.h"
#include "common/Cond.h"

/**
 * DBObjectMap: Implements ObjectMap in terms of KeyValueDB
 *
 * Prefix space structure:
 *
 * @see complete_prefix
 * @see user_prefix
 * @see sys_prefix
 *
 * - HOBJECT_TO_SEQ: Contains leaf mapping from hobject_t->seq and
 *                   corresponding omap header
 * - SYS_PREFIX: GLOBAL_STATE_KEY - contains next seq number
 *                                  @see State
 *                                  @see write_state
 *                                  @see init
 *                                  @see generate_new_header
 * - USER_PREFIX + header_key(header->seq) + USER_PREFIX
 *              : key->value for header->seq
 * - USER_PREFIX + header_key(header->seq) + COMPLETE_PREFIX: see below
 * - USER_PREFIX + header_key(header->seq) + XATTR_PREFIX: xattrs
 * - USER_PREFIX + header_key(header->seq) + SYS_PREFIX
 *              : USER_HEADER_KEY - omap header for header->seq
 *              : HEADER_KEY - encoding of header for header->seq
 *
 * For each node (represented by a header), we
 * store three mappings: the key mapping, the complete mapping, and the parent.
 * The complete mapping (COMPLETE_PREFIX space) is key->key.  Each x->y entry in
 * this mapping indicates that the key mapping contains all entries on [x,y).
 * Note, max string is represented by "", so ""->"" indicates that the parent
 * is unnecessary (@see rm_keys).  When looking up a key not contained in the
 * the complete set, we have to check the parent if we don't find it in the
 * key set.  During rm_keys, we copy keys from the parent and update the
 * complete set to reflect the change @see rm_keys.
 */
class DBObjectMap : public ObjectMap {
public:
  boost::scoped_ptr<KeyValueDB> db;

  /**
   * Serializes access to next_seq as well as the in_use set
   */
  Mutex header_lock;
  Cond header_cond;
  Cond map_header_cond;

  /**
   * Set of headers currently in use
   */
  set<uint64_t> in_use;
  set<hobject_t> map_header_in_use;

  DBObjectMap(KeyValueDB *db) : db(db),
				header_lock("DBOBjectMap")
    {}

  int set_keys(
    const hobject_t &hoid,
    const map<string, bufferlist> &set
    );

  int set_header(
    const hobject_t &hoid,
    const bufferlist &bl
    );

  int get_header(
    const hobject_t &hoid,
    bufferlist *bl
    );

  int clear(
    const hobject_t &hoid
    );

  int rm_keys(
    const hobject_t &hoid,
    const set<string> &to_clear
    );

  int get(
    const hobject_t &hoid,
    bufferlist *header,
    map<string, bufferlist> *out
    );

  int get_keys(
    const hobject_t &hoid,
    set<string> *keys
    );

  int get_values(
    const hobject_t &hoid,
    const set<string> &keys,
    map<string, bufferlist> *out
    );

  int check_keys(
    const hobject_t &hoid,
    const set<string> &keys,
    set<string> *out
    );

  int get_xattrs(
    const hobject_t &hoid,
    const set<string> &to_get,
    map<string, bufferlist> *out
    );

  int get_all_xattrs(
    const hobject_t &hoid,
    set<string> *out
    );

  int set_xattrs(
    const hobject_t &hoid,
    const map<string, bufferlist> &to_set
    );

  int remove_xattrs(
    const hobject_t &hoid,
    const set<string> &to_remove
    );

  int clone(
    const hobject_t &hoid,
    const hobject_t &target
    );

  /// Read initial state from backing store
  int init(bool upgrade = false);

  /// Upgrade store to current version
  int upgrade();

  /// Consistency check, debug, there must be no parallel writes
  bool check(std::ostream &out);

  /// Ensure that all previous operations are durable
  int sync();

  ObjectMapIterator get_iterator(const hobject_t &hoid);

  static const string USER_PREFIX;
  static const string XATTR_PREFIX;
  static const string SYS_PREFIX;
  static const string COMPLETE_PREFIX;
  static const string HEADER_KEY;
  static const string USER_HEADER_KEY;
  static const string GLOBAL_STATE_KEY;
  static const string HOBJECT_TO_SEQ;

  /// Legacy
  static const string LEAF_PREFIX;
  static const string REVERSE_LEAF_PREFIX;

  /// persistent state for store @see generate_header
  struct State {
    __u8 v;
    uint64_t seq;
    State() : v(0), seq(1) {}
    State(uint64_t seq) : v(0), seq(seq) {}

    void encode(bufferlist &bl) const {
      ENCODE_START(2, 1, bl);
      ::encode(v, bl);
      ::encode(seq, bl);
      ENCODE_FINISH(bl);
    }

    void decode(bufferlist::iterator &bl) {
      DECODE_START(2, bl);
      if (struct_v >= 2)
	::decode(v, bl);
      else
	v = 0;
      ::decode(seq, bl);
      DECODE_FINISH(bl);
    }

    void dump(Formatter *f) const {
      f->dump_unsigned("seq", seq);
    }

    static void generate_test_instances(list<State*> &o) {
      o.push_back(new State(0));
      o.push_back(new State(20));
    }
  } state;

  struct _Header {
    uint64_t seq;
    uint64_t parent;
    uint64_t num_children;

    coll_t c;
    hobject_t hoid;

    void encode(bufferlist &bl) const {
      ENCODE_START(1, 1, bl);
      ::encode(seq, bl);
      ::encode(parent, bl);
      ::encode(num_children, bl);
      ::encode(c, bl);
      ::encode(hoid, bl);
      ENCODE_FINISH(bl);
    }

    void decode(bufferlist::iterator &bl) {
      DECODE_START(1, bl);
      ::decode(seq, bl);
      ::decode(parent, bl);
      ::decode(num_children, bl);
      ::decode(c, bl);
      ::decode(hoid, bl);
      DECODE_FINISH(bl);
    }

    void dump(Formatter *f) const {
      f->dump_unsigned("seq", seq);
      f->dump_unsigned("parent", parent);
      f->dump_unsigned("num_children", num_children);
      f->dump_stream("coll") << c;
      f->dump_stream("oid") << hoid;
    }

    static void generate_test_instances(list<_Header*> &o) {
      o.push_back(new _Header);
      o.push_back(new _Header);
      o.back()->parent = 20;
      o.back()->seq = 30;
    }

    _Header() : seq(0), parent(0), num_children(1) {}
  };

  /// String munging (public for testing)
  static string hobject_key(const hobject_t &hoid);
  static string hobject_key_v0(coll_t c, const hobject_t &hoid);
  static bool parse_hobject_key_v0(const string &in,
				   coll_t *c, hobject_t *hoid);
private:
  /// Implicit lock on Header->seq
  typedef std::tr1::shared_ptr<_Header> Header;

  string map_header_key(const hobject_t &hoid);
  string header_key(uint64_t seq);
  string complete_prefix(Header header);
  string user_prefix(Header header);
  string sys_prefix(Header header);
  string xattr_prefix(Header header);
  string sys_parent_prefix(_Header header);
  string sys_parent_prefix(Header header) {
    return sys_parent_prefix(*header);
  }

  class EmptyIteratorImpl : public ObjectMapIteratorImpl {
  public:
    int seek_to_first() { return 0; }
    int seek_to_last() { return 0; }
    int upper_bound(const string &after) { return 0; }
    int lower_bound(const string &to) { return 0; }
    bool valid() { return false; }
    int next() { assert(0); return 0; }
    string key() { assert(0); return ""; }
    bufferlist value() { assert(0); return bufferlist(); }
    int status() { return 0; }
  };


  /// Iterator
  class DBObjectMapIteratorImpl : public ObjectMapIteratorImpl {
  public:
    DBObjectMap *map;

    /// NOTE: implicit lock on header->seq AND for all ancestors
    Header header;

    /// parent_iter == NULL iff no parent
    std::tr1::shared_ptr<DBObjectMapIteratorImpl> parent_iter;
    KeyValueDB::Iterator key_iter;
    KeyValueDB::Iterator complete_iter;

    /// cur_iter points to currently valid iterator
    std::tr1::shared_ptr<ObjectMapIteratorImpl> cur_iter;
    int r;

    /// init() called, key_iter, complete_iter, parent_iter filled in
    bool ready;
    /// past end
    bool invalid;

    DBObjectMapIteratorImpl(DBObjectMap *map, Header header) :
      map(map), header(header), r(0), ready(false), invalid(true) {}
    int seek_to_first();
    int seek_to_last();
    int upper_bound(const string &after);
    int lower_bound(const string &to);
    bool valid();
    int next();
    string key();
    bufferlist value();
    int status();

    bool on_parent() {
      return cur_iter == parent_iter;
    }

    /// skips to next valid parent entry
    int next_parent();

    /// Tests whether to_test is in complete region
    int in_complete_region(const string &to_test, ///< [in] key to test
			   string *begin,         ///< [out] beginning of region
			   string *end            ///< [out] end of region
      ); ///< @returns true if to_test is in the complete region, else false

  private:
    int init();
    bool valid_parent();
    int adjust();
  };

  typedef std::tr1::shared_ptr<DBObjectMapIteratorImpl> DBObjectMapIterator;
  DBObjectMapIterator _get_iterator(Header header) {
    return DBObjectMapIterator(new DBObjectMapIteratorImpl(this, header));
  }

  /// sys

  /// Removes node corresponding to header
  void clear_header(Header header, KeyValueDB::Transaction t);

  /// Set node containing input to new contents
  void set_header(Header input, KeyValueDB::Transaction t);

  /// Remove leaf node corresponding to hoid in c
  void remove_map_header(const hobject_t &hoid,
			 Header header,
			 KeyValueDB::Transaction t);

  /// Set leaf node for c and hoid to the value of header
  void set_map_header(const hobject_t &hoid, _Header header,
		      KeyValueDB::Transaction t);

  /// Lookup or create header for c hoid
  Header lookup_create_map_header(const hobject_t &hoid,
				  KeyValueDB::Transaction t);

  /**
   * Generate new header for c hoid with new seq number
   *
   * Has the side effect of syncronously saving the new DBObjectMap state
   */
  Header _generate_new_header(const hobject_t &hoid, Header parent);
  Header generate_new_header(const hobject_t &hoid, Header parent) {
    Mutex::Locker l(header_lock);
    return _generate_new_header(hoid, parent);
  }

  /// Lookup leaf header for c hoid
  Header _lookup_map_header(const hobject_t &hoid);
  Header lookup_map_header(const hobject_t &hoid) {
    Mutex::Locker l(header_lock);
    return _lookup_map_header(hoid);
  }

  /// Lookup header node for input
  Header lookup_parent(Header input);


  /// Helpers
  int _get_header(Header header, bufferlist *bl);

  /// Scan keys in header into out_keys and out_values (if nonnull)
  int scan(Header header,
	   const set<string> &in_keys,
	   set<string> *out_keys,
	   map<string, bufferlist> *out_values);

  /// Remove header and all related prefixes
  int _clear(Header header,
	     KeyValueDB::Transaction t);
  /// Adds to t operations necessary to add new_complete to the complete set
  int merge_new_complete(Header header,
			 const map<string, string> &new_complete,
			 DBObjectMapIterator iter,
			 KeyValueDB::Transaction t);

  /// Writes out State (mainly next_seq)
  int write_state(bool sync = false);

  /// 0 if the complete set now contains all of key space, < 0 on error, 1 else
  int need_parent(DBObjectMapIterator iter);

  /// Copies header entry from parent @see rm_keys
  int copy_up_header(Header header,
		     KeyValueDB::Transaction t);

  /// Sets header @see set_header
  void _set_header(Header header, const bufferlist &bl,
		   KeyValueDB::Transaction t);

  /** 
   * Removes map header lock once Header is out of scope
   * @see lookup_map_header
   */
  class RemoveMapHeaderOnDelete {
  public:
    DBObjectMap *db;
    hobject_t obj;
    RemoveMapHeaderOnDelete(DBObjectMap *db, const hobject_t &obj) :
      db(db), obj(obj) {}
    void operator() (_Header *header) {
      Mutex::Locker l(db->header_lock);
      db->map_header_in_use.erase(obj);
      db->map_header_cond.Signal();
      delete header;
    }
  };

  /** 
   * Removes header seq lock once Header is out of scope
   * @see lookup_parent
   * @see generate_new_header
   */
  class RemoveOnDelete {
  public:
    DBObjectMap *db;
    RemoveOnDelete(DBObjectMap *db) :
      db(db) {}
    void operator() (_Header *header) {
      Mutex::Locker l(db->header_lock);
      db->in_use.erase(header->seq);
      db->header_cond.Signal();
      delete header;
    }
  };
  friend class RemoveOnDelete;
};
WRITE_CLASS_ENCODER(DBObjectMap::_Header)
WRITE_CLASS_ENCODER(DBObjectMap::State)

#endif