leveldb_transaction.cc revision 6e8cce623b6e4fe0c9e4af605d675dd9d0338c38 
1// Copyright (c) 2013 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "content/browser/indexed_db/leveldb/leveldb_transaction.h"
6
7#include "base/logging.h"
8#include "base/metrics/histogram.h"
9#include "base/time/time.h"
10#include "content/browser/indexed_db/leveldb/leveldb_database.h"
11#include "content/browser/indexed_db/leveldb/leveldb_write_batch.h"
12#include "third_party/leveldatabase/src/include/leveldb/db.h"
13
14using base::StringPiece;
15
16namespace content {
17
18LevelDBTransaction::LevelDBTransaction(LevelDBDatabase* db)
19    : db_(db),
20      snapshot_(db),
21      comparator_(db->Comparator()),
22      data_comparator_(comparator_),
23      data_(data_comparator_),
24      finished_(false) {}
25
26LevelDBTransaction::Record::Record() : deleted(false) {}
27LevelDBTransaction::Record::~Record() {}
28
29void LevelDBTransaction::Clear() {
30  for (DataType::iterator it = data_.begin(); it != data_.end(); ++it) {
31    delete it->second;
32  }
33  data_.clear();
34}
35
36LevelDBTransaction::~LevelDBTransaction() { Clear(); }
37
38void LevelDBTransaction::Set(const StringPiece& key,
39                             std::string* value,
40                             bool deleted) {
41  DCHECK(!finished_);
42  DataType::iterator it = data_.find(key);
43
44  if (it == data_.end()) {
45    Record* record = new Record();
46    record->key.assign(key.begin(), key.end() - key.begin());
47    record->value.swap(*value);
48    record->deleted = deleted;
49    data_[record->key] = record;
50    NotifyIterators();
51    return;
52  }
53
54  it->second->value.swap(*value);
55  it->second->deleted = deleted;
56}
57
58void LevelDBTransaction::Put(const StringPiece& key, std::string* value) {
59  Set(key, value, false);
60}
61
62void LevelDBTransaction::Remove(const StringPiece& key) {
63  std::string empty;
64  Set(key, &empty, true);
65}
66
67leveldb::Status LevelDBTransaction::Get(const StringPiece& key,
68                                        std::string* value,
69                                        bool* found) {
70  *found = false;
71  DCHECK(!finished_);
72  std::string string_key(key.begin(), key.end() - key.begin());
73  DataType::const_iterator it = data_.find(string_key);
74
75  if (it != data_.end()) {
76    if (it->second->deleted)
77      return leveldb::Status::OK();
78
79    *value = it->second->value;
80    *found = true;
81    return leveldb::Status::OK();
82  }
83
84  leveldb::Status s = db_->Get(key, value, found, &snapshot_);
85  if (!s.ok())
86    DCHECK(!*found);
87  return s;
88}
89
90leveldb::Status LevelDBTransaction::Commit() {
91  DCHECK(!finished_);
92
93  if (data_.empty()) {
94    finished_ = true;
95    return leveldb::Status::OK();
96  }
97
98  base::TimeTicks begin_time = base::TimeTicks::Now();
99  scoped_ptr<LevelDBWriteBatch> write_batch = LevelDBWriteBatch::Create();
100
101  for (DataType::iterator iterator = data_.begin(); iterator != data_.end();
102       ++iterator) {
103    if (!iterator->second->deleted)
104      write_batch->Put(iterator->first, iterator->second->value);
105    else
106      write_batch->Remove(iterator->first);
107  }
108
109  leveldb::Status s = db_->Write(*write_batch);
110  if (s.ok()) {
111    Clear();
112    finished_ = true;
113    UMA_HISTOGRAM_TIMES("WebCore.IndexedDB.LevelDB.Transaction.CommitTime",
114                         base::TimeTicks::Now() - begin_time);
115  }
116  return s;
117}
118
119void LevelDBTransaction::Rollback() {
120  DCHECK(!finished_);
121  finished_ = true;
122  Clear();
123}
124
125scoped_ptr<LevelDBIterator> LevelDBTransaction::CreateIterator() {
126  return TransactionIterator::Create(this).PassAs<LevelDBIterator>();
127}
128
129scoped_ptr<LevelDBTransaction::DataIterator>
130LevelDBTransaction::DataIterator::Create(LevelDBTransaction* transaction) {
131  return make_scoped_ptr(new DataIterator(transaction));
132}
133
134bool LevelDBTransaction::DataIterator::IsValid() const {
135  return iterator_ != data_->end();
136}
137
138leveldb::Status LevelDBTransaction::DataIterator::SeekToLast() {
139  iterator_ = data_->end();
140  if (iterator_ != data_->begin())
141    --iterator_;
142  return leveldb::Status::OK();
143}
144
145leveldb::Status LevelDBTransaction::DataIterator::Seek(
146    const StringPiece& target) {
147  iterator_ = data_->lower_bound(target);
148  return leveldb::Status::OK();
149}
150
151leveldb::Status LevelDBTransaction::DataIterator::Next() {
152  DCHECK(IsValid());
153  ++iterator_;
154  return leveldb::Status::OK();
155}
156
157leveldb::Status LevelDBTransaction::DataIterator::Prev() {
158  DCHECK(IsValid());
159  if (iterator_ != data_->begin())
160    --iterator_;
161  else
162    iterator_ = data_->end();
163  return leveldb::Status::OK();
164}
165
166StringPiece LevelDBTransaction::DataIterator::Key() const {
167  DCHECK(IsValid());
168  return iterator_->first;
169}
170
171StringPiece LevelDBTransaction::DataIterator::Value() const {
172  DCHECK(IsValid());
173  DCHECK(!IsDeleted());
174  return iterator_->second->value;
175}
176
177bool LevelDBTransaction::DataIterator::IsDeleted() const {
178  DCHECK(IsValid());
179  return iterator_->second->deleted;
180}
181
182LevelDBTransaction::DataIterator::~DataIterator() {}
183
184LevelDBTransaction::DataIterator::DataIterator(LevelDBTransaction* transaction)
185    : data_(&transaction->data_),
186      iterator_(data_->end()) {}
187
188scoped_ptr<LevelDBTransaction::TransactionIterator>
189LevelDBTransaction::TransactionIterator::Create(
190    scoped_refptr<LevelDBTransaction> transaction) {
191  return make_scoped_ptr(new TransactionIterator(transaction));
192}
193
194LevelDBTransaction::TransactionIterator::TransactionIterator(
195    scoped_refptr<LevelDBTransaction> transaction)
196    : transaction_(transaction),
197      comparator_(transaction_->comparator_),
198      data_iterator_(DataIterator::Create(transaction_.get())),
199      db_iterator_(transaction_->db_->CreateIterator(&transaction_->snapshot_)),
200      current_(0),
201      direction_(FORWARD),
202      data_changed_(false) {
203  transaction_->RegisterIterator(this);
204}
205
206LevelDBTransaction::TransactionIterator::~TransactionIterator() {
207  transaction_->UnregisterIterator(this);
208}
209
210bool LevelDBTransaction::TransactionIterator::IsValid() const {
211  return !!current_;
212}
213
214leveldb::Status LevelDBTransaction::TransactionIterator::SeekToLast() {
215  leveldb::Status s = data_iterator_->SeekToLast();
216  DCHECK(s.ok());
217  s = db_iterator_->SeekToLast();
218  if (!s.ok())
219    return s;
220  direction_ = REVERSE;
221
222  HandleConflictsAndDeletes();
223  SetCurrentIteratorToLargestKey();
224  return s;
225}
226
227leveldb::Status LevelDBTransaction::TransactionIterator::Seek(
228    const StringPiece& target) {
229  leveldb::Status s = data_iterator_->Seek(target);
230  DCHECK(s.ok());
231  s = db_iterator_->Seek(target);
232  if (!s.ok())
233    return s;
234  direction_ = FORWARD;
235
236  HandleConflictsAndDeletes();
237  SetCurrentIteratorToSmallestKey();
238  return s;
239}
240
241leveldb::Status LevelDBTransaction::TransactionIterator::Next() {
242  DCHECK(IsValid());
243  if (data_changed_)
244    RefreshDataIterator();
245
246  leveldb::Status s;
247  if (direction_ != FORWARD) {
248    // Ensure the non-current iterator is positioned after Key().
249
250    LevelDBIterator* non_current = (current_ == db_iterator_.get())
251                                       ? data_iterator_.get()
252                                       : db_iterator_.get();
253
254    non_current->Seek(Key());
255    if (non_current->IsValid() &&
256        !comparator_->Compare(non_current->Key(), Key())) {
257      // Take an extra step so the non-current key is
258      // strictly greater than Key().
259      s = non_current->Next();
260      if (!s.ok())
261        return s;
262    }
263    DCHECK(!non_current->IsValid() ||
264           comparator_->Compare(non_current->Key(), Key()) > 0);
265
266    direction_ = FORWARD;
267  }
268
269  s = current_->Next();
270  if (!s.ok())
271    return s;
272  HandleConflictsAndDeletes();
273  SetCurrentIteratorToSmallestKey();
274  return leveldb::Status::OK();
275}
276
277leveldb::Status LevelDBTransaction::TransactionIterator::Prev() {
278  DCHECK(IsValid());
279  leveldb::Status s;
280  if (data_changed_)
281    RefreshDataIterator();
282
283  if (direction_ != REVERSE) {
284    // Ensure the non-current iterator is positioned before Key().
285
286    LevelDBIterator* non_current = (current_ == db_iterator_.get())
287                                       ? data_iterator_.get()
288                                       : db_iterator_.get();
289
290    s = non_current->Seek(Key());
291    if (!s.ok())
292      return s;
293    if (non_current->IsValid()) {
294      // Iterator is at first entry >= Key().
295      // Step back once to entry < key.
296      // This is why we don't check for the keys being the same before
297      // stepping, like we do in Next() above.
298      non_current->Prev();
299    } else {
300      // Iterator has no entries >= Key(). Position at last entry.
301      non_current->SeekToLast();
302    }
303    DCHECK(!non_current->IsValid() ||
304           comparator_->Compare(non_current->Key(), Key()) < 0);
305
306    direction_ = REVERSE;
307  }
308
309  s = current_->Prev();
310  if (!s.ok())
311    return s;
312  HandleConflictsAndDeletes();
313  SetCurrentIteratorToLargestKey();
314  return leveldb::Status::OK();
315}
316
317StringPiece LevelDBTransaction::TransactionIterator::Key() const {
318  DCHECK(IsValid());
319  if (data_changed_)
320    RefreshDataIterator();
321  return current_->Key();
322}
323
324StringPiece LevelDBTransaction::TransactionIterator::Value() const {
325  DCHECK(IsValid());
326  if (data_changed_)
327    RefreshDataIterator();
328  return current_->Value();
329}
330
331void LevelDBTransaction::TransactionIterator::DataChanged() {
332  data_changed_ = true;
333}
334
335void LevelDBTransaction::TransactionIterator::RefreshDataIterator() const {
336  DCHECK(data_changed_);
337
338  data_changed_ = false;
339
340  if (data_iterator_->IsValid() && data_iterator_.get() == current_) {
341    return;
342  }
343
344  if (db_iterator_->IsValid()) {
345    // There could be new records in data that we should iterate over.
346
347    if (direction_ == FORWARD) {
348      // Try to seek data iterator to something greater than the db iterator.
349      data_iterator_->Seek(db_iterator_->Key());
350      if (data_iterator_->IsValid() &&
351          !comparator_->Compare(data_iterator_->Key(), db_iterator_->Key())) {
352        // If equal, take another step so the data iterator is strictly greater.
353        data_iterator_->Next();
354      }
355    } else {
356      // If going backward, seek to a key less than the db iterator.
357      DCHECK_EQ(REVERSE, direction_);
358      data_iterator_->Seek(db_iterator_->Key());
359      if (data_iterator_->IsValid())
360        data_iterator_->Prev();
361    }
362  }
363}
364
365bool LevelDBTransaction::TransactionIterator::DataIteratorIsLower() const {
366  return comparator_->Compare(data_iterator_->Key(), db_iterator_->Key()) < 0;
367}
368
369bool LevelDBTransaction::TransactionIterator::DataIteratorIsHigher() const {
370  return comparator_->Compare(data_iterator_->Key(), db_iterator_->Key()) > 0;
371}
372
373void LevelDBTransaction::TransactionIterator::HandleConflictsAndDeletes() {
374  bool loop = true;
375
376  while (loop) {
377    loop = false;
378
379    if (data_iterator_->IsValid() && db_iterator_->IsValid() &&
380        !comparator_->Compare(data_iterator_->Key(), db_iterator_->Key())) {
381      // For equal keys, the data iterator takes precedence, so move the
382      // database iterator another step.
383      if (direction_ == FORWARD)
384        db_iterator_->Next();
385      else
386        db_iterator_->Prev();
387    }
388
389    // Skip over delete markers in the data iterator until it catches up with
390    // the db iterator.
391    if (data_iterator_->IsValid() && data_iterator_->IsDeleted()) {
392      if (direction_ == FORWARD &&
393          (!db_iterator_->IsValid() || DataIteratorIsLower())) {
394        data_iterator_->Next();
395        loop = true;
396      } else if (direction_ == REVERSE &&
397                 (!db_iterator_->IsValid() || DataIteratorIsHigher())) {
398        data_iterator_->Prev();
399        loop = true;
400      }
401    }
402  }
403}
404
405void
406LevelDBTransaction::TransactionIterator::SetCurrentIteratorToSmallestKey() {
407  LevelDBIterator* smallest = 0;
408
409  if (data_iterator_->IsValid())
410    smallest = data_iterator_.get();
411
412  if (db_iterator_->IsValid()) {
413    if (!smallest ||
414        comparator_->Compare(db_iterator_->Key(), smallest->Key()) < 0)
415      smallest = db_iterator_.get();
416  }
417
418  current_ = smallest;
419}
420
421void LevelDBTransaction::TransactionIterator::SetCurrentIteratorToLargestKey() {
422  LevelDBIterator* largest = 0;
423
424  if (data_iterator_->IsValid())
425    largest = data_iterator_.get();
426
427  if (db_iterator_->IsValid()) {
428    if (!largest ||
429        comparator_->Compare(db_iterator_->Key(), largest->Key()) > 0)
430      largest = db_iterator_.get();
431  }
432
433  current_ = largest;
434}
435
436void LevelDBTransaction::RegisterIterator(TransactionIterator* iterator) {
437  DCHECK(iterators_.find(iterator) == iterators_.end());
438  iterators_.insert(iterator);
439}
440
441void LevelDBTransaction::UnregisterIterator(TransactionIterator* iterator) {
442  DCHECK(iterators_.find(iterator) != iterators_.end());
443  iterators_.erase(iterator);
444}
445
446void LevelDBTransaction::NotifyIterators() {
447  for (std::set<TransactionIterator*>::iterator i = iterators_.begin();
448       i != iterators_.end();
449       ++i) {
450    TransactionIterator* transaction_iterator = *i;
451    transaction_iterator->DataChanged();
452  }
453}
454
455scoped_ptr<LevelDBDirectTransaction> LevelDBDirectTransaction::Create(
456    LevelDBDatabase* db) {
457  return make_scoped_ptr(new LevelDBDirectTransaction(db));
458}
459
460LevelDBDirectTransaction::LevelDBDirectTransaction(LevelDBDatabase* db)
461    : db_(db), write_batch_(LevelDBWriteBatch::Create()), finished_(false) {}
462
463LevelDBDirectTransaction::~LevelDBDirectTransaction() {
464  write_batch_->Clear();
465}
466
467void LevelDBDirectTransaction::Put(const StringPiece& key,
468                                   const std::string* value) {
469  DCHECK(!finished_);
470  write_batch_->Put(key, *value);
471}
472
473leveldb::Status LevelDBDirectTransaction::Get(const StringPiece& key,
474                                              std::string* value,
475                                              bool* found) {
476  *found = false;
477  DCHECK(!finished_);
478
479  leveldb::Status s = db_->Get(key, value, found);
480  DCHECK(s.ok() || !*found);
481  return s;
482}
483
484void LevelDBDirectTransaction::Remove(const StringPiece& key) {
485  DCHECK(!finished_);
486  write_batch_->Remove(key);
487}
488
489leveldb::Status LevelDBDirectTransaction::Commit() {
490  DCHECK(!finished_);
491
492  leveldb::Status s = db_->Write(*write_batch_);
493  if (s.ok()) {
494    finished_ = true;
495    write_batch_->Clear();
496  }
497  return s;
498}
499
500}  // namespace content
501