diff options
author | Ben Caimano <ben.caimano@mongodb.com> | 2019-12-16 20:00:19 +0000 |
---|---|---|
committer | evergreen <evergreen@mongodb.com> | 2019-12-16 20:00:19 +0000 |
commit | aa3121c79560efb2c0c7b808eac05e0cf08f20f6 (patch) | |
tree | bb54fb475f2a60041666e6c0e93a8affb3b99492 | |
parent | 3cb95d93cb9f64b9224b9e11f26e0d5a75dae590 (diff) | |
download | mongo-aa3121c79560efb2c0c7b808eac05e0cf08f20f6.tar.gz |
SERVER-45168 Create add-only syncronized list type
-rw-r--r-- | src/mongo/util/SConscript | 1 | ||||
-rw-r--r-- | src/mongo/util/registry_list.h | 194 | ||||
-rw-r--r-- | src/mongo/util/registry_list_test.cpp | 159 |
3 files changed, 354 insertions, 0 deletions
diff --git a/src/mongo/util/SConscript b/src/mongo/util/SConscript index 5b9ced06500..06ae54e98cc 100644 --- a/src/mongo/util/SConscript +++ b/src/mongo/util/SConscript @@ -578,6 +578,7 @@ icuEnv.CppUnitTest( 'procparser_test.cpp' if env.TargetOSIs('linux') else [], 'producer_consumer_queue_test.cpp', 'progress_meter_test.cpp', + 'registry_list_test.cpp', 'represent_as_test.cpp', 'safe_num_test.cpp', 'secure_zero_memory_test.cpp', diff --git a/src/mongo/util/registry_list.h b/src/mongo/util/registry_list.h new file mode 100644 index 00000000000..f451cb78a46 --- /dev/null +++ b/src/mongo/util/registry_list.h @@ -0,0 +1,194 @@ +/** + * Copyright (C) 2018-present MongoDB, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the Server Side Public License, version 1, + * as published by MongoDB, Inc. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * Server Side Public License for more details. + * + * You should have received a copy of the Server Side Public License + * along with this program. If not, see + * <http://www.mongodb.com/licensing/server-side-public-license>. + * + * As a special exception, the copyright holders give permission to link the + * code of portions of this program with the OpenSSL library under certain + * conditions as described in each individual source file and distribute + * linked combinations including the program with the OpenSSL library. You + * must comply with the Server Side Public License in all respects for + * all of the code used other than as permitted herein. If you modify file(s) + * with this exception, you may extend this exception to your version of the + * file(s), but you are not obligated to do so. If you do not wish to do so, + * delete this exception statement from your version. If you delete this + * exception statement from all source files in the program, then also delete + * it in the license file. + */ + +#pragma once + +#include <deque> +#include <memory> + +#include "mongo/stdx/mutex.h" +#include "mongo/util/concepts.h" + +namespace mongo { + +/** + * Simple generator-type iterator + * + * This Iterator caches/obscures the underlying data type to allow subclasses to wrap its more() + * and next() functions. + */ +template <typename DataT> +class RegistryListIterator { +public: + using DataType = DataT; + using ElementType = typename DataT::value_type; + + explicit RegistryListIterator(DataT data) : _data{std::move(data)} {} + + virtual ~RegistryListIterator() = default; + + /** + * Return the next element and advance the iterator + */ + auto next() { + if (!more()) { + return ElementType(); + } + + return _data[_index++]; + } + + /** + * Return true if there are more elements available + */ + virtual bool more() const { + return _index < _data.size(); + } + +private: + DataType _data; + + size_t _index = 0; +}; + +/** + * A synchronized add-only list of elements + * + * A RegistryList is intended to allow concurrent iteration, insertion, and access with minimal + * amounts of resource contention. If each element in the list is a pointer or index, the overhead + * of "deactivated" elements is minimal. + * + * This class does no lifetime management for its elements besides construction and destruction. If + * you use it to store pointers, the pointed-to memory should be immortal. + */ +TEMPLATE(typename ElementT) +REQUIRES(std::is_default_constructible_v<ElementT>) +class RegistryList { +public: + using ElementType = ElementT; + using DataType = std::deque<ElementT>; + using Iterator = RegistryListIterator<DataType>; + + virtual ~RegistryList() = default; + + /** + * Add an element to the list + * + * @returns The index of the new pointer element + */ + size_t add(ElementType ptr) { + stdx::lock_guard lk(_m); + + _data.emplace_back(std::move(ptr)); + return _data.size() - 1; + } + + /** + * Returns an element at the given index within the list + */ + ElementType at(size_t index) const { + stdx::lock_guard lk(_m); + + if (index >= _data.size()) { + // If index is past our synchronized end on the deque, then indexing it will be UB. + return ElementType(); + } + + return _data[index]; + } + + /** + * Return the total number of elements in this list + */ + size_t size() const { + stdx::lock_guard lk(_m); + + return _data.size(); + } + + /** + * Return a copy of the underlying data structure + */ + DataType data() const { + stdx::lock_guard lk(_m); + + return _data; + } + + /** + * Return an iterator for this list + * + * This iterator copies the state of the list at the time of capture. If additional elements are + * added after this function is invoked, they will not be visible via the Iterator. + */ + auto iter() const { + return Iterator(data()); + } + +private: + mutable stdx::mutex _m; // NOLINT + DataType _data; +}; + +/** + * Wrap the basic RegistryList concept to handle weak_ptrs + */ +TEMPLATE(typename T) +REQUIRES(std::is_constructible_v<std::weak_ptr<T>>) +class WeakPtrRegistryList : public RegistryList<std::weak_ptr<T>> { +public: + using ElementType = std::weak_ptr<T>; + using BaseList = RegistryList<ElementType>; + using DataType = typename BaseList::DataType; + + class Iterator final : public BaseList::Iterator { + public: + using BaseList::Iterator::Iterator; + + auto next() { + return BaseList::Iterator::next().lock(); + } + }; + + virtual ~WeakPtrRegistryList() = default; + + auto add(const std::shared_ptr<T>& ptr) { + return BaseList::add(std::weak_ptr<T>(ptr)); + } + + auto at(size_t index) const { + return BaseList::at(index).lock(); + } + + auto iter() const { + return Iterator(BaseList::data()); + } +}; + +} // namespace mongo diff --git a/src/mongo/util/registry_list_test.cpp b/src/mongo/util/registry_list_test.cpp new file mode 100644 index 00000000000..cca1761b44d --- /dev/null +++ b/src/mongo/util/registry_list_test.cpp @@ -0,0 +1,159 @@ +/** + * Copyright (C) 2019-present MongoDB, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the Server Side Public License, version 1, + * as published by MongoDB, Inc. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * Server Side Public License for more details. + * + * You should have received a copy of the Server Side Public License + * along with this program. If not, see + * <http://www.mongodb.com/licensing/server-side-public-license>. + * + * As a special exception, the copyright holders give permission to link the + * code of portions of this program with the OpenSSL library under certain + * conditions as described in each individual source file and distribute + * linked combinations including the program with the OpenSSL library. You + * must comply with the Server Side Public License in all respects for + * all of the code used other than as permitted herein. If you modify file(s) + * with this exception, you may extend this exception to your version of the + * file(s), but you are not obligated to do so. If you do not wish to do so, + * delete this exception statement from your version. If you delete this + * exception statement from all source files in the program, then also delete + * it in the license file. + */ + +#include "mongo/util/registry_list.h" + +#include <vector> + +#include <boost/optional.hpp> + +#include "mongo/stdx/condition_variable.h" +#include "mongo/stdx/mutex.h" +#include "mongo/stdx/thread.h" +#include "mongo/unittest/barrier.h" +#include "mongo/unittest/unittest.h" + +namespace mongo { +namespace { + +TEST(RegistryList, MixedOperationsSingleThread) { + /** + * Show that iterleaved add() and iter() calls function as expected + */ + + RegistryList<boost::optional<int>> list; + + for (int i = 0; i < 10000; ++i) { + // Get our cached iterator first + auto iter = list.iter(); + + { + // Add a new value + auto index = list.add(i); + + // Each index should be i since we are adding in sequence + ASSERT_EQ(index, i); + } + + { + // Each index from before should be accessible + int j = 0; + for (; j <= i; ++j) { + // For each value that was already added, the value should also be the index + ASSERT_EQ(*list.at(j), j); + } + + // Values outside the list should be default constructed + ASSERT_FALSE(list.at(j)); + } + + { + // The iterator we got out should have the state before we added the newest element + int count = 0; + while (iter.more()) { + auto val = iter.next(); + ASSERT_EQ(*val, count); + + ++count; + } + + ASSERT_EQ(count, list.size() - 1); + ASSERT_FALSE(iter.next()); + } + } +} + +TEST(RegistryList, ConcurrentAdd) { + /** + * Show that multiple concurrent add() and iter() calls function to expectation + */ + RegistryList<boost::optional<size_t>> list; + + constexpr size_t kThreads = 4; + constexpr size_t kAdds = 100000; + + + struct State { + stdx::mutex m; // NOLINT + size_t workersDone = 0; + } state; + + unittest::Barrier barrier{kThreads + 1}; + + auto addWorkerFunc = [&] { + // Each worker adds a fixed number of elements + barrier.countDownAndWait(); + + for (size_t i = 0; i < kAdds; ++i) { + list.add(i); + } + + stdx::lock_guard lk(state.m); + ++state.workersDone; + }; + + auto iteratorFunc = [&] { + // The iterator thread repeatedly tries to iterate over the list while add()s are happening. + barrier.countDownAndWait(); + + while ([&] { + stdx::lock_guard lk(state.m); + return state.workersDone != kThreads; + }()) { + // The list never shrinks over the course of iteration and probably grows, this proves + // that rule via iter() and size() + + auto lastSize = list.size(); + auto iter = list.iter(); + + auto count = 0; + while (auto e = iter.next()) { + ++count; + } + + ASSERT_LTE(lastSize, count); + ASSERT_LTE(count, list.size()); + } + }; + + std::vector<stdx::thread> threads; + threads.emplace_back(iteratorFunc); + for (size_t i = 0; i < kThreads; ++i) { + threads.emplace_back(addWorkerFunc); + } + + for (auto& thread : threads) { + thread.join(); + } + + ASSERT_EQ(list.size(), kThreads * kAdds); +} + +} // namespace +} // namespace mongo |