73d019b85e358fb6f2731809af8083b9c5698910
[ep-engine.git] / src / linked_list.h
1 /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /*
3  *     Copyright 2017 Couchbase, Inc
4  *
5  *   Licensed under the Apache License, Version 2.0 (the "License");
6  *   you may not use this file except in compliance with the License.
7  *   You may obtain a copy of the License at
8  *
9  *       http://www.apache.org/licenses/LICENSE-2.0
10  *
11  *   Unless required by applicable law or agreed to in writing, software
12  *   distributed under the License is distributed on an "AS IS" BASIS,
13  *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *   See the License for the specific language governing permissions and
15  *   limitations under the License.
16  */
17
18 /**
19  * This header file contains the class definition of one of the implementation
20  * of the abstract class SequenceList
21  */
22
23 #pragma once
24
25 #include "atomic.h"
26 #include "config.h"
27 #include "monotonic.h"
28 #include "seqlist.h"
29 #include "stored-value.h"
30
31 #include <boost/intrusive/list.hpp>
32 #include <platform/non_negative_counter.h>
33 #include <relaxed_atomic.h>
34
35 /* This option will configure "list" to use the member hook */
36 using MemberHookOption =
37         boost::intrusive::member_hook<OrderedStoredValue,
38                                       boost::intrusive::list_member_hook<>,
39                                       &OrderedStoredValue::seqno_hook>;
40
41 /* This list will use the member hook */
42 using OrderedLL = boost::intrusive::list<OrderedStoredValue, MemberHookOption>;
43
44 /**
45  * Class that represents a range of sequence numbers.
46  * SeqRange is closed, that is, both begin and end are inclusive.
47  *
48  * Note: begin <= 0 is considered an default/inactive range and can be set
49  *       only by ctor or by reset.
50  */
51 class SeqRange {
52 public:
53     SeqRange(const seqno_t beginVal, const seqno_t endVal)
54         : end(endVal), begin(beginVal) {
55         if ((end < begin) || (begin < 0)) {
56             throw std::invalid_argument("Trying to create invalid SeqRange: [" +
57                                         std::to_string(begin) + ", " +
58                                         std::to_string(end) + "]");
59         }
60     }
61
62     SeqRange& operator=(const SeqRange& other) {
63         begin = other.begin;
64         end = other.end;
65         return *this;
66     }
67
68     /**
69      * Returns true if the range overlaps with another.
70      */
71     bool overlaps(const SeqRange& other) const {
72         return std::max(begin, other.begin) <= std::min(end, other.end);
73     }
74
75     /**
76      *  Returns true if the seqno falls in the range
77      */
78     bool fallsInRange(const seqno_t seqno) const {
79         return (seqno >= begin) && (seqno <= end);
80     }
81
82     void reset() {
83         begin = 0;
84         end = 0;
85     }
86
87     seqno_t getBegin() const {
88         return begin;
89     }
90
91     void setBegin(const seqno_t start) {
92         if ((start <= 0) || (start > end)) {
93             throw std::invalid_argument(
94                     "Trying to set incorrect begin " + std::to_string(start) +
95                     " on SeqRange: [" + std::to_string(begin) + ", " +
96                     std::to_string(end) + "]");
97         }
98         begin = start;
99     }
100
101     seqno_t getEnd() const {
102         return end;
103     }
104
105 private:
106     seqno_t end;
107     seqno_t begin;
108 };
109
110 /**
111  * This class implements SequenceList as a basic doubly linked list.
112  * Uses boost intrusive list for doubly linked list implementation.
113  *
114  * Intrusive hook is to be added to OrderedStoredValue for it to be used in the
115  * BasicLinkedList. Once in the BasicLinkedList, OrderedStoredValue is now
116  * shared between HashTable and BasicLinkedList.
117  *
118  * BasicLinkedList sees only the hook for next and prev; HashTable
119  * see only the hook for hashtable chaining.
120  *
121  * But there should be an agreement on the deletion (invalidation of next and
122  * prev link; chaining link) of the elements between these 2 class objects.
123  * Currently,
124  * (i) HashTable owns a OrderedStoredValue (as a unique_ptr) that is not stale.
125  * (ii) It relinquishes the ownership by marking it stale. This happens when
126  *      deduplication is not possible and we want to keep an old value around.
127  * (iii) BasicLinkedList deletes the stale OrderedStoredValues.
128  * (iv) During a Hashtable clear (full or partial), which happens during
129  *      VBucket delete or rollback, we first remove the element from
130  *      BasicLinkedList (invalidate next, prev links) and then delete from the
131  *      hashtable.
132  */
133 class BasicLinkedList : public SequenceList {
134 public:
135     BasicLinkedList(uint16_t vbucketId, EPStats& st);
136
137     ~BasicLinkedList();
138
139     void appendToList(std::lock_guard<std::mutex>& seqLock,
140                       OrderedStoredValue& v) override;
141
142     SequenceList::UpdateStatus updateListElem(
143             std::lock_guard<std::mutex>& seqLock,
144             OrderedStoredValue& v) override;
145
146     std::tuple<ENGINE_ERROR_CODE, std::vector<UniqueItemPtr>, seqno_t>
147     rangeRead(seqno_t start, seqno_t end) override;
148
149     void updateHighSeqno(std::lock_guard<std::mutex>& highSeqnoLock,
150                          const OrderedStoredValue& v) override;
151
152     void updateHighestDedupedSeqno(std::lock_guard<std::mutex>& highSeqnoLock,
153                                    const OrderedStoredValue& v) override;
154
155     void markItemStale(StoredValue::UniquePtr ownedSv) override;
156
157     size_t purgeTombstones() override;
158
159     void updateNumDeletedItems(bool oldDeleted, bool newDeleted) override;
160
161     uint64_t getNumStaleItems() const override;
162
163     size_t getStaleValueBytes() const override;
164
165     size_t getStaleMetadataBytes() const override;
166
167     uint64_t getNumDeletedItems() const override;
168
169     uint64_t getNumItems() const override;
170
171     uint64_t getHighSeqno() const override;
172
173     uint64_t getHighestDedupedSeqno() const override;
174
175     seqno_t getHighestPurgedDeletedSeqno() const override;
176
177     uint64_t getRangeReadBegin() const override;
178
179     uint64_t getRangeReadEnd() const override;
180
181     std::mutex& getHighSeqnosLock() const override;
182
183     void dump() const override;
184
185 protected:
186     /* Underlying data structure that holds the items in an Ordered Sequence */
187     OrderedLL seqList;
188
189     /**
190      * Lock that serializes writes (append, update, purgeTombstones) on
191      * 'seqList'
192      */
193     mutable std::mutex writeLock;
194
195     /**
196      * Used to mark of the range where point-in-time snapshot is happening.
197      * To get a valid point-in-time snapshot and for correct list iteration we
198      * must not de-duplicate an item in the list in this range.
199      */
200     SeqRange readRange;
201
202     /**
203      * Lock that protects readRange.
204      * We use spinlock here since the lock is held only for very small time
205      * periods.
206      */
207     mutable SpinLock rangeLock;
208
209     /**
210      * Lock protecting the highSeqno and highestDedupedSeqno.
211      */
212     mutable std::mutex highSeqnosLock;
213
214     /**
215      * Lock that serializes range reads on the 'seqList' - i.e. serializes
216      * the addition / removal of range reads from the set in-flight.
217      * We need to serialize range reads because, range reads set a list level
218      * range in which items are read. If we have multiple range reads then we
219      * must handle the races in the updation of the range to have most inclusive
220      * range.
221      * For now we use this lock to allow only one range read at a time.
222      *
223      * It is also additionally used in purgeTombstones() to prevent the
224      * creation of any new rangeReads while purge is in-progress - see
225      * detailed comments there.
226      */
227     std::mutex rangeReadLock;
228
229     /* Overall memory consumed by (stale) OrderedStoredValues owned by the
230        list */
231     Couchbase::RelaxedAtomic<size_t> staleSize;
232
233     /* Metadata memory consumed by (stale) OrderedStoredValues owned by the
234        list */
235     Couchbase::RelaxedAtomic<size_t> staleMetaDataSize;
236
237 private:
238     OrderedLL::iterator purgeListElem(OrderedLL::iterator it);
239
240     /**
241      * We need to keep track of the highest seqno separately because there is a
242      * small window wherein the last element of the list (though in correct
243      * order) does not have a seqno.
244      *
245      * highseqno is monotonically increasing and is reset to a lower value
246      * only in case of a rollback.
247      *
248      * Guarded by rangeLock.
249      */
250     Monotonic<seqno_t> highSeqno;
251
252     /**
253      * We need to this to send out point-in-time snapshots in range read
254      *
255      * highestDedupedSeqno is monotonically increasing and is reset to a lower
256      * value only in case of a rollback.
257      */
258     Monotonic<seqno_t> highestDedupedSeqno;
259
260     /**
261      * The sequence number of the highest purged element.
262      *
263      * This should be non-decrementing, apart from a rollback where it will be
264      * reset.
265      */
266     Monotonic<seqno_t> highestPurgedDeletedSeqno;
267
268     /**
269      * Indicates the number of elements in the list that are stale (old,
270      * duplicate values). Stale items are owned by the list and hence must
271      * periodically clean them up.
272      */
273     cb::NonNegativeCounter<uint64_t> numStaleItems;
274
275     /**
276      * Indicates the number of logically deleted items in the list.
277      * Since we are append-only, distributed cache supporting incremental
278      * replication, we need to keep deleted items for while and periodically
279      * purge them
280      */
281     cb::NonNegativeCounter<uint64_t> numDeletedItems;
282
283     /* Used only to log debug messages */
284     const uint16_t vbid;
285
286     /* Ep engine stats handle to track stats */
287     EPStats& st;
288
289     friend std::ostream& operator<<(std::ostream& os,
290                                     const BasicLinkedList& ll);
291 };
292
293 /// Outputs a textual description of the BasicLinkedList
294 std::ostream& operator <<(std::ostream& os, const BasicLinkedList& ll);