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);