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 (DataType::iterator it = data_.begin(); it != data_.end(); ++it) { 31 delete it->second; 32 } 33 data_.clear(); 34 } 35 36 LevelDBTransaction::~LevelDBTransaction() { Clear(); } 37 38 void 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 58 void LevelDBTransaction::Put(const StringPiece& key, std::string* value) { 59 Set(key, value, false); 60 } 61 62 void LevelDBTransaction::Remove(const StringPiece& key) { 63 std::string empty; 64 Set(key, &empty, true); 65 } 66 67 leveldb::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 90 leveldb::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 119 void LevelDBTransaction::Rollback() { 120 DCHECK(!finished_); 121 finished_ = true; 122 Clear(); 123 } 124 125 scoped_ptr<LevelDBIterator> LevelDBTransaction::CreateIterator() { 126 return TransactionIterator::Create(this).PassAs<LevelDBIterator>(); 127 } 128 129 scoped_ptr<LevelDBTransaction::DataIterator> 130 LevelDBTransaction::DataIterator::Create(LevelDBTransaction* transaction) { 131 return make_scoped_ptr(new DataIterator(transaction)); 132 } 133 134 bool LevelDBTransaction::DataIterator::IsValid() const { 135 return iterator_ != data_->end(); 136 } 137 138 leveldb::Status LevelDBTransaction::DataIterator::SeekToLast() { 139 iterator_ = data_->end(); 140 if (iterator_ != data_->begin()) 141 --iterator_; 142 return leveldb::Status::OK(); 143 } 144 145 leveldb::Status LevelDBTransaction::DataIterator::Seek( 146 const StringPiece& target) { 147 iterator_ = data_->lower_bound(target); 148 return leveldb::Status::OK(); 149 } 150 151 leveldb::Status LevelDBTransaction::DataIterator::Next() { 152 DCHECK(IsValid()); 153 ++iterator_; 154 return leveldb::Status::OK(); 155 } 156 157 leveldb::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 166 StringPiece LevelDBTransaction::DataIterator::Key() const { 167 DCHECK(IsValid()); 168 return iterator_->first; 169 } 170 171 StringPiece LevelDBTransaction::DataIterator::Value() const { 172 DCHECK(IsValid()); 173 DCHECK(!IsDeleted()); 174 return iterator_->second->value; 175 } 176 177 bool LevelDBTransaction::DataIterator::IsDeleted() const { 178 DCHECK(IsValid()); 179 return iterator_->second->deleted; 180 } 181 182 LevelDBTransaction::DataIterator::~DataIterator() {} 183 184 LevelDBTransaction::DataIterator::DataIterator(LevelDBTransaction* transaction) 185 : data_(&transaction->data_), 186 iterator_(data_->end()) {} 187 188 scoped_ptr<LevelDBTransaction::TransactionIterator> 189 LevelDBTransaction::TransactionIterator::Create( 190 scoped_refptr<LevelDBTransaction> transaction) { 191 return make_scoped_ptr(new TransactionIterator(transaction)); 192 } 193 194 LevelDBTransaction::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 206 LevelDBTransaction::TransactionIterator::~TransactionIterator() { 207 transaction_->UnregisterIterator(this); 208 } 209 210 bool LevelDBTransaction::TransactionIterator::IsValid() const { 211 return !!current_; 212 } 213 214 leveldb::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 227 leveldb::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 241 leveldb::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 277 leveldb::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 317 StringPiece LevelDBTransaction::TransactionIterator::Key() const { 318 DCHECK(IsValid()); 319 if (data_changed_) 320 RefreshDataIterator(); 321 return current_->Key(); 322 } 323 324 StringPiece LevelDBTransaction::TransactionIterator::Value() const { 325 DCHECK(IsValid()); 326 if (data_changed_) 327 RefreshDataIterator(); 328 return current_->Value(); 329 } 330 331 void LevelDBTransaction::TransactionIterator::DataChanged() { 332 data_changed_ = true; 333 } 334 335 void 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 365 bool LevelDBTransaction::TransactionIterator::DataIteratorIsLower() const { 366 return comparator_->Compare(data_iterator_->Key(), db_iterator_->Key()) < 0; 367 } 368 369 bool LevelDBTransaction::TransactionIterator::DataIteratorIsHigher() const { 370 return comparator_->Compare(data_iterator_->Key(), db_iterator_->Key()) > 0; 371 } 372 373 void 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 405 void 406 LevelDBTransaction::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 421 void 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 436 void LevelDBTransaction::RegisterIterator(TransactionIterator* iterator) { 437 DCHECK(iterators_.find(iterator) == iterators_.end()); 438 iterators_.insert(iterator); 439 } 440 441 void LevelDBTransaction::UnregisterIterator(TransactionIterator* iterator) { 442 DCHECK(iterators_.find(iterator) != iterators_.end()); 443 iterators_.erase(iterator); 444 } 445 446 void 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 455 scoped_ptr<LevelDBDirectTransaction> LevelDBDirectTransaction::Create( 456 LevelDBDatabase* db) { 457 return make_scoped_ptr(new LevelDBDirectTransaction(db)); 458 } 459 460 LevelDBDirectTransaction::LevelDBDirectTransaction(LevelDBDatabase* db) 461 : db_(db), write_batch_(LevelDBWriteBatch::Create()), finished_(false) {} 462 463 LevelDBDirectTransaction::~LevelDBDirectTransaction() { 464 write_batch_->Clear(); 465 } 466 467 void LevelDBDirectTransaction::Put(const StringPiece& key, 468 const std::string* value) { 469 DCHECK(!finished_); 470 write_batch_->Put(key, *value); 471 } 472 473 leveldb::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 484 void LevelDBDirectTransaction::Remove(const StringPiece& key) { 485 DCHECK(!finished_); 486 write_batch_->Remove(key); 487 } 488 489 leveldb::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