1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
2 //  This source code is licensed under both the GPLv2 (found in the
3 //  COPYING file in the root directory) and Apache 2.0 License
4 //  (found in the LICENSE.Apache file in the root directory).
5 //
6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
9 
10 #pragma once
11 #include <vector>
12 
13 #include "rocksdb/db.h"
14 
15 namespace ROCKSDB_NAMESPACE {
16 
17 class SnapshotList;
18 
19 // Snapshots are kept in a doubly-linked list in the DB.
20 // Each SnapshotImpl corresponds to a particular sequence number.
21 class SnapshotImpl : public Snapshot {
22  public:
23   SequenceNumber number_;  // const after creation
24   // It indicates the smallest uncommitted data at the time the snapshot was
25   // taken. This is currently used by WritePrepared transactions to limit the
26   // scope of queries to IsInSnpashot.
27   SequenceNumber min_uncommitted_ = kMinUnCommittedSeq;
28 
GetSequenceNumber()29   virtual SequenceNumber GetSequenceNumber() const override { return number_; }
30 
31  private:
32   friend class SnapshotList;
33 
34   // SnapshotImpl is kept in a doubly-linked circular list
35   SnapshotImpl* prev_;
36   SnapshotImpl* next_;
37 
38   SnapshotList* list_;                 // just for sanity checks
39 
40   int64_t unix_time_;
41 
42   // Will this snapshot be used by a Transaction to do write-conflict checking?
43   bool is_write_conflict_boundary_;
44 };
45 
46 class SnapshotList {
47  public:
SnapshotList()48   SnapshotList() {
49     list_.prev_ = &list_;
50     list_.next_ = &list_;
51     list_.number_ = 0xFFFFFFFFL;      // placeholder marker, for debugging
52     // Set all the variables to make UBSAN happy.
53     list_.list_ = nullptr;
54     list_.unix_time_ = 0;
55     list_.is_write_conflict_boundary_ = false;
56     count_ = 0;
57   }
58 
59   // No copy-construct.
60   SnapshotList(const SnapshotList&) = delete;
61 
empty()62   bool empty() const { return list_.next_ == &list_; }
oldest()63   SnapshotImpl* oldest() const { assert(!empty()); return list_.next_; }
newest()64   SnapshotImpl* newest() const { assert(!empty()); return list_.prev_; }
65 
New(SnapshotImpl * s,SequenceNumber seq,uint64_t unix_time,bool is_write_conflict_boundary)66   SnapshotImpl* New(SnapshotImpl* s, SequenceNumber seq, uint64_t unix_time,
67                     bool is_write_conflict_boundary) {
68     s->number_ = seq;
69     s->unix_time_ = unix_time;
70     s->is_write_conflict_boundary_ = is_write_conflict_boundary;
71     s->list_ = this;
72     s->next_ = &list_;
73     s->prev_ = list_.prev_;
74     s->prev_->next_ = s;
75     s->next_->prev_ = s;
76     count_++;
77     return s;
78   }
79 
80   // Do not responsible to free the object.
Delete(const SnapshotImpl * s)81   void Delete(const SnapshotImpl* s) {
82     assert(s->list_ == this);
83     s->prev_->next_ = s->next_;
84     s->next_->prev_ = s->prev_;
85     count_--;
86   }
87 
88   // retrieve all snapshot numbers up until max_seq. They are sorted in
89   // ascending order (with no duplicates).
90   std::vector<SequenceNumber> GetAll(
91       SequenceNumber* oldest_write_conflict_snapshot = nullptr,
92       const SequenceNumber& max_seq = kMaxSequenceNumber) const {
93     std::vector<SequenceNumber> ret;
94     GetAll(&ret, oldest_write_conflict_snapshot, max_seq);
95     return ret;
96   }
97 
98   void GetAll(std::vector<SequenceNumber>* snap_vector,
99               SequenceNumber* oldest_write_conflict_snapshot = nullptr,
100               const SequenceNumber& max_seq = kMaxSequenceNumber) const {
101     std::vector<SequenceNumber>& ret = *snap_vector;
102     // So far we have no use case that would pass a non-empty vector
103     assert(ret.size() == 0);
104 
105     if (oldest_write_conflict_snapshot != nullptr) {
106       *oldest_write_conflict_snapshot = kMaxSequenceNumber;
107     }
108 
109     if (empty()) {
110       return;
111     }
112     const SnapshotImpl* s = &list_;
113     while (s->next_ != &list_) {
114       if (s->next_->number_ > max_seq) {
115         break;
116       }
117       // Avoid duplicates
118       if (ret.empty() || ret.back() != s->next_->number_) {
119         ret.push_back(s->next_->number_);
120       }
121 
122       if (oldest_write_conflict_snapshot != nullptr &&
123           *oldest_write_conflict_snapshot == kMaxSequenceNumber &&
124           s->next_->is_write_conflict_boundary_) {
125         // If this is the first write-conflict boundary snapshot in the list,
126         // it is the oldest
127         *oldest_write_conflict_snapshot = s->next_->number_;
128       }
129 
130       s = s->next_;
131     }
132     return;
133   }
134 
135   // get the sequence number of the most recent snapshot
GetNewest()136   SequenceNumber GetNewest() {
137     if (empty()) {
138       return 0;
139     }
140     return newest()->number_;
141   }
142 
GetOldestSnapshotTime()143   int64_t GetOldestSnapshotTime() const {
144     if (empty()) {
145       return 0;
146     } else {
147       return oldest()->unix_time_;
148     }
149   }
150 
GetOldestSnapshotSequence()151   int64_t GetOldestSnapshotSequence() const {
152     if (empty()) {
153       return 0;
154     } else {
155       return oldest()->GetSequenceNumber();
156     }
157   }
158 
count()159   uint64_t count() const { return count_; }
160 
161  private:
162   // Dummy head of doubly-linked list of snapshots
163   SnapshotImpl list_;
164   uint64_t count_;
165 };
166 
167 }  // namespace ROCKSDB_NAMESPACE
168