MB-24151: Implement general range read iterator in seqlist
[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     SequenceList::RangeIterator makeRangeIterator() override;
184
185     void dump() const override;
186
187 protected:
188     /* Underlying data structure that holds the items in an Ordered Sequence */
189     OrderedLL seqList;
190
191     /**
192      * Lock that serializes writes (append, update, purgeTombstones) on
193      * 'seqList'
194      */
195     mutable std::mutex writeLock;
196
197     /**
198      * Used to mark of the range where point-in-time snapshot is happening.
199      * To get a valid point-in-time snapshot and for correct list iteration we
200      * must not de-duplicate an item in the list in this range.
201      */
202     SeqRange readRange;
203
204     /**
205      * Lock that protects readRange.
206      * We use spinlock here since the lock is held only for very small time
207      * periods.
208      */
209     mutable SpinLock rangeLock;
210
211     /**
212      * Lock protecting the highSeqno and highestDedupedSeqno.
213      */
214     mutable std::mutex highSeqnosLock;
215
216     /**
217      * Lock that serializes range reads on the 'seqList' - i.e. serializes
218      * the addition / removal of range reads from the set in-flight.
219      * We need to serialize range reads because, range reads set a list level
220      * range in which items are read. If we have multiple range reads then we
221      * must handle the races in the updation of the range to have most inclusive
222      * range.
223      * For now we use this lock to allow only one range read at a time.
224      *
225      * It is also additionally used in purgeTombstones() to prevent the
226      * creation of any new rangeReads while purge is in-progress - see
227      * detailed comments there.
228      */
229     std::mutex rangeReadLock;
230
231     /* Overall memory consumed by (stale) OrderedStoredValues owned by the
232        list */
233     Couchbase::RelaxedAtomic<size_t> staleSize;
234
235     /* Metadata memory consumed by (stale) OrderedStoredValues owned by the
236        list */
237     Couchbase::RelaxedAtomic<size_t> staleMetaDataSize;
238
239 private:
240     OrderedLL::iterator purgeListElem(OrderedLL::iterator it);
241
242     /**
243      * We need to keep track of the highest seqno separately because there is a
244      * small window wherein the last element of the list (though in correct
245      * order) does not have a seqno.
246      *
247      * highseqno is monotonically increasing and is reset to a lower value
248      * only in case of a rollback.
249      *
250      * Guarded by rangeLock.
251      */
252     Monotonic<seqno_t> highSeqno;
253
254     /**
255      * We need to this to send out point-in-time snapshots in range read
256      *
257      * highestDedupedSeqno is monotonically increasing and is reset to a lower
258      * value only in case of a rollback.
259      */
260     Monotonic<seqno_t> highestDedupedSeqno;
261
262     /**
263      * The sequence number of the highest purged element.
264      *
265      * This should be non-decrementing, apart from a rollback where it will be
266      * reset.
267      */
268     Monotonic<seqno_t> highestPurgedDeletedSeqno;
269
270     /**
271      * Indicates the number of elements in the list that are stale (old,
272      * duplicate values). Stale items are owned by the list and hence must
273      * periodically clean them up.
274      */
275     cb::NonNegativeCounter<uint64_t> numStaleItems;
276
277     /**
278      * Indicates the number of logically deleted items in the list.
279      * Since we are append-only, distributed cache supporting incremental
280      * replication, we need to keep deleted items for while and periodically
281      * purge them
282      */
283     cb::NonNegativeCounter<uint64_t> numDeletedItems;
284
285     /* Used only to log debug messages */
286     const uint16_t vbid;
287
288     /* Ep engine stats handle to track stats */
289     EPStats& st;
290
291     friend std::ostream& operator<<(std::ostream& os,
292                                     const BasicLinkedList& ll);
293
294     class RangeIteratorLL : public SequenceList::RangeIteratorImpl {
295     public:
296         RangeIteratorLL(BasicLinkedList& ll);
297
298         ~RangeIteratorLL();
299
300         OrderedStoredValue& operator*() const override;
301
302         RangeIteratorLL& operator++() override;
303
304         seqno_t curr() const override {
305             return itrRange.getBegin();
306         }
307
308         seqno_t end() const override {
309             return itrRange.getEnd();
310         }
311
312     private:
313         /* Ref to BasicLinkedList object which is iterated by this iterator.
314            By setting the member variables of the list obj appropriately we
315            ensure that iterator is not invalidated */
316         BasicLinkedList& list;
317
318         /* The current list element pointed by the iterator */
319         OrderedLL::iterator currIt;
320
321         /* Lock holder which allows having only one iterator at a time */
322         std::unique_lock<std::mutex> readLockHolder;
323
324         /* Current range of the iterator */
325         SeqRange itrRange;
326     };
327
328     friend class RangeIteratorLL;
329 };
330
331 /// Outputs a textual description of the BasicLinkedList
332 std::ostream& operator <<(std::ostream& os, const BasicLinkedList& ll);