src/pre_link_document_context.h
src/replicationthrottle.cc
src/linked_list.cc
+ src/seqlist.cc
src/string_utils.cc
src/storeddockey.cc
src/stored-value.cc
return highSeqnosLock;
}
+SequenceList::RangeIterator BasicLinkedList::makeRangeIterator() {
+ return SequenceList::RangeIterator(
+ std::make_unique<RangeIteratorLL>(*this));
+}
+
void BasicLinkedList::dump() const {
std::cerr << *this << std::endl;
}
}
return it;
}
+
+BasicLinkedList::RangeIteratorLL::RangeIteratorLL(BasicLinkedList& ll)
+ : list(ll), readLockHolder(list.rangeReadLock), itrRange(0, 0) {
+ std::lock_guard<SpinLock> lh(list.rangeLock);
+ if (list.highSeqno < 1) {
+ /* No need of holding a lock for the snapshot as there are no items;
+ Also iterator range is at default (0, 0) */
+ readLockHolder.unlock();
+ return;
+ }
+
+ /* Iterator to the beginning of linked list */
+ currIt = list.seqList.begin();
+
+ /* Mark the snapshot range on linked list. The range that can be read by the
+ iterator is inclusive of the start and the end. */
+ list.readRange = SeqRange(currIt->getBySeqno(), list.highSeqno);
+
+ /* Keep the range in the iterator obj. We store the range end seqno as one
+ higher than the end seqno that can be read by this iterator.
+ This is because, we must identify the end point of the iterator, and
+ we the read is inclusive of the end points of list.readRange.
+
+ Further, since use the class 'SeqRange' for 'itrRange' we cannot use
+ curr() == end() + 1 to identify the end point because 'SeqRange' does
+ not internally allow curr > end */
+ itrRange = SeqRange(currIt->getBySeqno(), list.highSeqno + 1);
+}
+
+BasicLinkedList::RangeIteratorLL::~RangeIteratorLL() {
+ std::lock_guard<SpinLock> lh(list.rangeLock);
+ list.readRange.reset();
+ /* As readLockHolder goes out of scope here, it will automatically release
+ the snapshot read lock on the linked list */
+}
+
+OrderedStoredValue& BasicLinkedList::RangeIteratorLL::operator*() const {
+ if (curr() >= end()) {
+ /* We can't read beyond the range end */
+ throw std::out_of_range(
+ "BasicLinkedList::RangeIteratorLL::operator*()"
+ ": Trying to read beyond range end seqno " +
+ std::to_string(end()));
+ }
+ return *currIt;
+}
+
+BasicLinkedList::RangeIteratorLL& BasicLinkedList::RangeIteratorLL::
+operator++() {
+ if (curr() >= end()) {
+ throw std::out_of_range(
+ "BasicLinkedList::RangeIteratorLL::operator++()"
+ ": Trying to move the iterator beyond range end"
+ " seqno " +
+ std::to_string(end()));
+ }
+
+ /* Check if the iterator is pointing to the last element. Increment beyond
+ the last element indicates the end of the iteration */
+ if (curr() == itrRange.getEnd() - 1) {
+ std::lock_guard<SpinLock> lh(list.rangeLock);
+ /* Release snapshot read lock on the linked list */
+ list.readRange.reset();
+ readLockHolder.unlock();
+
+ /* Update the begin to end() so the client can see that the iteration
+ has ended */
+ itrRange.setBegin(end());
+ return *this;
+ }
+
+ ++currIt;
+ {
+ /* As the iterator moves we reduce the snapshot range being read on the
+ linked list. This helps reduce the stale items in the list during
+ heavy update load from the front end */
+ std::lock_guard<SpinLock> lh(list.rangeLock);
+ list.readRange.setBegin(currIt->getBySeqno());
+ }
+
+ /* Also update the current range stored in the iterator obj */
+ itrRange.setBegin(currIt->getBySeqno());
+
+ return *this;
+}
std::mutex& getHighSeqnosLock() const override;
+ SequenceList::RangeIterator makeRangeIterator() override;
+
void dump() const override;
protected:
friend std::ostream& operator<<(std::ostream& os,
const BasicLinkedList& ll);
+
+ class RangeIteratorLL : public SequenceList::RangeIteratorImpl {
+ public:
+ RangeIteratorLL(BasicLinkedList& ll);
+
+ ~RangeIteratorLL();
+
+ OrderedStoredValue& operator*() const override;
+
+ RangeIteratorLL& operator++() override;
+
+ seqno_t curr() const override {
+ return itrRange.getBegin();
+ }
+
+ seqno_t end() const override {
+ return itrRange.getEnd();
+ }
+
+ private:
+ /* Ref to BasicLinkedList object which is iterated by this iterator.
+ By setting the member variables of the list obj appropriately we
+ ensure that iterator is not invalidated */
+ BasicLinkedList& list;
+
+ /* The current list element pointed by the iterator */
+ OrderedLL::iterator currIt;
+
+ /* Lock holder which allows having only one iterator at a time */
+ std::unique_lock<std::mutex> readLockHolder;
+
+ /* Current range of the iterator */
+ SeqRange itrRange;
+ };
+
+ friend class RangeIteratorLL;
};
/// Outputs a textual description of the BasicLinkedList
--- /dev/null
+/* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
+/*
+ * Copyright 2017 Couchbase, Inc
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <mutex>
+#include "linked_list.h"
+
+SequenceList::RangeIterator::RangeIterator(
+ std::unique_ptr<RangeIteratorImpl> rangeIterImpl)
+ : rangeIterImpl(std::move(rangeIterImpl)) {
+}
+
+OrderedStoredValue& SequenceList::RangeIterator::operator*() const {
+ return *(*rangeIterImpl);
+}
+
+SequenceList::RangeIterator& SequenceList::RangeIterator::operator++() {
+ ++(*rangeIterImpl);
+ return *this;
+}
+
+seqno_t SequenceList::RangeIterator::curr() {
+ return rangeIterImpl->curr();
+}
+
+seqno_t SequenceList::RangeIterator::end() {
+ return rangeIterImpl->end();
+}
* rangeRead and Clean Up
*/
class SequenceList {
+protected:
+ /**
+ * Abstract base class for implementation of range iterators in derived
+ * classes of SequenceList.
+ *
+ * (a) The API is for unidirectional (forward only) iterator.
+ * (b) Iterator cannot be invalidated while in use.
+ * (c) Reading all the items from the iterator results in point-in-time
+ * snapshot.
+ * (d) Only 1 iterator can be created for now.
+ * (e) Currently iterator can be created only from start till end
+ */
+ class RangeIteratorImpl {
+ public:
+ virtual ~RangeIteratorImpl() {
+ }
+
+ /**
+ * Returns the stored item at iterator's position
+ */
+ virtual OrderedStoredValue& operator*() const = 0;
+
+ /**
+ * Pre increment of the iterator position
+ *
+ * Note: We do not allow post increment for now as we support only
+ * one iterator at a time. (hence, we don't create a temp copy
+ * of the iterator obj)
+ */
+ virtual RangeIteratorImpl& operator++() = 0;
+
+ /**
+ * Curr iterator position, indicated by the seqno of the item at that
+ * position
+ */
+ virtual seqno_t curr() const = 0;
+
+ /**
+ * End position of iterator, indicated by the seqno > highest_seqno
+ * in the iterator range
+ */
+ virtual seqno_t end() const = 0;
+ };
+
public:
/**
* Indicates whether the updateListElem is successful or the list is
*/
enum class UpdateStatus { Success, Append };
+ /**
+ * RangeIterator for a SequenceList objects.
+ *
+ * The iterator is unidirectional (forward only) and cannot be invalidated
+ * while in use. That means reading the items in the iterator results in a
+ * valid point-in-time snapshot. But this adds a caveat that while an
+ * iterator instance is active, certain invariants are to be met to get the
+ * snapshot, and this happens at the expense of increased memory usage.
+ *
+ * Implementation follows the pimpl idiom. This class serves as a wrapper
+ * for the abstract base class that defines the APIs for range iteration on
+ * the derived concrete classes of the SequenceList. It calls the range
+ * iterators of the concrete classes polymorphically at runtime. However
+ * clients get this statically typed "RangeIterator" object when they
+ * request for an iterator for a SequenceList object.
+ *
+ * Usage:
+ * 1. Create an iterator instance using SequenceList::makeRangeIterator()
+ * 2. Iterate (read) through all the list elements.
+ * 3. Delete the iterator.
+ * Note: (a) Do not hold the iterator for long, as it will result in stale
+ * items in list and hence increased memory usage.
+ * (b) Make sure to delete the iterator after using it.
+ * (c) For now, we allow on one RangeIterator. Try to create more
+ * iterators will result in the create call(s) being blocked.
+ */
+ class RangeIterator {
+ public:
+ RangeIterator(std::unique_ptr<RangeIteratorImpl> rangeIterImpl);
+
+ /* Needed for MSVC.
+ MSVC does not do "return value optimization" if copy constructor is
+ defined before move constructor
+ (http://stackoverflow.com/questions/29459040)
+ */
+ RangeIterator(RangeIterator&& other)
+ : rangeIterImpl(std::move(other.rangeIterImpl)) {
+ }
+
+ RangeIterator(RangeIterator& other) = delete;
+
+ /**
+ * Returns the stored item at iterator's position
+ */
+ OrderedStoredValue& operator*() const;
+
+ /**
+ * Pre increment of the iterator position
+ */
+ RangeIterator& operator++();
+
+ /**
+ * Curr iterator position, indicated by the seqno of the item at that
+ * position
+ */
+ seqno_t curr();
+
+ /**
+ * Curr iterator position, indicated by the seqno of the item at that
+ * position
+ */
+ seqno_t end();
+
+ private:
+ /* Pointer to the abstract class of range iterator implementation */
+ std::unique_ptr<RangeIteratorImpl> rangeIterImpl;
+ };
+
virtual ~SequenceList() {
}
virtual std::mutex& getHighSeqnosLock() const = 0;
/**
+ * Returns a range iterator for the underlying SequenceList obj
+ */
+ virtual SequenceList::RangeIterator makeRangeIterator() = 0;
+
+ /**
* Debug - prints a representation of the list to stderr.
*/
virtual void dump() const = 0;
* To be called when there is range read.
*/
void updateItemDuringRangeRead(seqno_t highSeqno, const std::string& key) {
+ const std::string val("data");
+
/* Get a fake sequence lock */
std::mutex fakeSeqLock;
std::lock_guard<std::mutex> lg(fakeSeqLock);
EXPECT_EQ(SequenceList::UpdateStatus::Append,
basicLL->updateListElem(lg, *osv));
+
+ /* Release the current sv from the HT */
+ StoredDocKey sKey = makeStoredDocKey(key);
+ auto hbl = ht.getLockedBucket(sKey);
+ auto ownedSv = ht.unlocked_release(hbl, osv->getKey());
+ basicLL->markItemStale(std::move(ownedSv));
+
+ /* Add a new storedvalue for the append */
+ Item itm(sKey,
+ 0,
+ 0,
+ val.data(),
+ val.length(),
+ /*ext_meta*/ nullptr,
+ /*ext_len*/ 0,
+ /*theCas*/ 0,
+ /*bySeqno*/ highSeqno + 1);
+ auto newSv = ht.unlocked_addNewStoredValue(hbl, itm);
+
+ basicLL->appendToList(lg, *(newSv->toOrderedStoredValue()));
+ std::lock_guard<std::mutex> highSeqnoLh(basicLL->getHighSeqnosLock());
+ basicLL->updateHighSeqno(highSeqnoLh, *(newSv->toOrderedStoredValue()));
}
/**
/* Update an item in the list when a fake range read is happening */
updateItemDuringRangeRead(numItems,
keyPrefix + std::to_string(numItems - 1));
+
+ /* Check if the new element is added correctly */
+ std::vector<seqno_t> expectedSeqno = {1, 2, 3, 4};
+ EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
}
TEST_F(BasicLinkedListTest, DeletedItem) {
EXPECT_EQ(svSize, basicLL->getStaleValueBytes());
EXPECT_EQ(svMetaDataSize, basicLL->getStaleMetadataBytes());
}
+
+TEST_F(BasicLinkedListTest, RangeIterator) {
+ const int numItems = 3;
+
+ /* Add 3 new items */
+ std::vector<seqno_t> expectedSeqno =
+ addNewItemsToList(1, std::string("key"), numItems);
+
+ auto itr = basicLL->makeRangeIterator();
+
+ std::vector<seqno_t> actualSeqno;
+
+ /* Read all the items with the iterator */
+ while (itr.curr() != itr.end()) {
+ actualSeqno.push_back((*itr).getBySeqno());
+ ++itr;
+ }
+ EXPECT_EQ(expectedSeqno, actualSeqno);
+}
+
+TEST_F(BasicLinkedListTest, RangeIteratorNoItems) {
+ auto itr = basicLL->makeRangeIterator();
+ /* Since there are no items in the list to iterate over, we expect itr start
+ to be end */
+ EXPECT_EQ(itr.curr(), itr.end());
+}
+
+TEST_F(BasicLinkedListTest, RangeIteratorSingleItem) {
+ /* Add an item */
+ std::vector<seqno_t> expectedSeqno =
+ addNewItemsToList(1, std::string("key"), 1);
+
+ auto itr = basicLL->makeRangeIterator();
+
+ std::vector<seqno_t> actualSeqno;
+ /* Read all the items with the iterator */
+ while (itr.curr() != itr.end()) {
+ actualSeqno.push_back((*itr).getBySeqno());
+ ++itr;
+ }
+ EXPECT_EQ(expectedSeqno, actualSeqno);
+}
+
+TEST_F(BasicLinkedListTest, RangeIteratorOverflow) {
+ const int numItems = 1;
+ bool caughtOutofRangeExcp = false;
+
+ /* Add an item */
+ addNewItemsToList(1, std::string("key"), numItems);
+
+ auto itr = basicLL->makeRangeIterator();
+
+ /* Iterator till end */
+ while (itr.curr() != itr.end()) {
+ ++itr;
+ }
+
+ /* Try iterating beyond the end and expect exception to be thrown */
+ try {
+ ++itr;
+ } catch (std::out_of_range& e) {
+ caughtOutofRangeExcp = true;
+ }
+ EXPECT_TRUE(caughtOutofRangeExcp);
+}
+
+TEST_F(BasicLinkedListTest, RangeIteratorDeletion) {
+ const int numItems = 3;
+
+ /* Add 3 new items */
+ std::vector<seqno_t> expectedSeqno =
+ addNewItemsToList(1, std::string("key"), numItems);
+
+ /* Check if second range reader can read items after the first one is
+ deleted */
+ for (int i = 0; i < 2; ++i) {
+ auto itr = basicLL->makeRangeIterator();
+ std::vector<seqno_t> actualSeqno;
+
+ /* Read all the items with the iterator */
+ while (itr.curr() != itr.end()) {
+ actualSeqno.push_back((*itr).getBySeqno());
+ ++itr;
+ }
+ EXPECT_EQ(expectedSeqno, actualSeqno);
+
+ /* itr is deleted as each time we loop */
+ }
+}
+
+TEST_F(BasicLinkedListTest, RangeIteratorAddNewItemDuringRead) {
+ const int numItems = 3;
+
+ /* Add 3 new items */
+ std::vector<seqno_t> expectedSeqno =
+ addNewItemsToList(1, std::string("key"), numItems);
+
+ {
+ auto itr = basicLL->makeRangeIterator();
+
+ std::vector<seqno_t> actualSeqno;
+
+ /* Read one item */
+ actualSeqno.push_back((*itr).getBySeqno());
+ ++itr;
+
+ /* Add a new item */
+ addNewItemsToList(numItems + 1 /* start */, std::string("key"), 1);
+
+ /* Read the other items */
+ while (itr.curr() != itr.end()) {
+ actualSeqno.push_back((*itr).getBySeqno());
+ ++itr;
+ }
+ EXPECT_EQ(expectedSeqno, actualSeqno);
+
+ /* itr is deleted */
+ }
+
+ /* Now create new iterator and if we can read all elements */
+ expectedSeqno.push_back(numItems + 1);
+
+ {
+ auto itr = basicLL->makeRangeIterator();
+ std::vector<seqno_t> actualSeqno;
+
+ /* Read the other items */
+ while (itr.curr() != itr.end()) {
+ actualSeqno.push_back((*itr).getBySeqno());
+ ++itr;
+ }
+ EXPECT_EQ(expectedSeqno, actualSeqno);
+ }
+}
+
+TEST_F(BasicLinkedListTest, RangeIteratorUpdateItemDuringRead) {
+ const int numItems = 3;
+ const std::string keyPrefix("key");
+
+ /* Add 3 new items */
+ std::vector<seqno_t> expectedSeqno =
+ addNewItemsToList(1, keyPrefix, numItems);
+
+ {
+ auto itr = basicLL->makeRangeIterator();
+
+ std::vector<seqno_t> actualSeqno;
+
+ /* Read one item */
+ actualSeqno.push_back((*itr).getBySeqno());
+ ++itr;
+
+ /* Update an item */
+ updateItemDuringRangeRead(numItems /*highSeqno*/,
+ keyPrefix + std::to_string(2));
+
+ /* Read the other items */
+ while (itr.curr() != itr.end()) {
+ actualSeqno.push_back((*itr).getBySeqno());
+ ++itr;
+ }
+ EXPECT_EQ(expectedSeqno, actualSeqno);
+
+ /* itr is deleted */
+ }
+
+ /* Now create new iterator and if we can read all elements */
+ expectedSeqno.push_back(numItems + 1);
+
+ {
+ auto itr = basicLL->makeRangeIterator();
+ std::vector<seqno_t> actualSeqno;
+
+ /* Read the other items */
+ while (itr.curr() != itr.end()) {
+ actualSeqno.push_back((*itr).getBySeqno());
+ ++itr;
+ }
+ EXPECT_EQ(expectedSeqno, actualSeqno);
+ }
+}
Code Review / ep-engine.git / commitdiff