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