content/browser/indexed_db/leveldb/leveldb_transaction.cc

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