SERVER-42892 Create set and key types for hierarchical locking

(cherry picked from commit 081a51065ac9b855a0d9e07d88701910b547ad96)

4 files changed, 519 insertions, 0 deletions

diff --git a/src/mongo/util/SConscript b/src/mongo/util/SConscript
index 0ec84ecf8d1..0d909a977da 100644
--- a/src/mongo/util/SConscript
+++ b/src/mongo/util/SConscript
@@ -539,6 +539,7 @@ icuEnv.CppUnitTest(
         'future_test_promise_int.cpp',
         'future_test_promise_void.cpp',
         'future_test_shared_future.cpp',
+        'hierarchical_acquisition_test.cpp',
         'icu_test.cpp',
         'invalidating_lru_cache_test.cpp',
         'itoa_test.cpp',
diff --git a/src/mongo/util/hierarchical_acquisition.h b/src/mongo/util/hierarchical_acquisition.h
new file mode 100644
index 00000000000..e4955088b9d
--- /dev/null
+++ b/src/mongo/util/hierarchical_acquisition.h
@@ -0,0 +1,262 @@
+/**
+ *    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.
+ */
+
+#pragma once
+
+#include <climits>
+#include <cstdint>
+
+#include "mongo/util/assert_util.h"
+
+namespace mongo {
+
+namespace hierachical_acquisition_detail {
+
+/**
+ * Hierarchical acquisition types are light-weight wrappers around bitwise math
+ *
+ * Each Level is a bitmap with a single bit set. The corresponding IndexType index for each Level is
+ * how many bits that level's bit is right shifted from the greatest bit in the internal ValueType
+ * value. So a Level 0 (L0) will be the bitmap 0X8000000000000000000000000. Likewise, a Level 63
+ * (L63) bitmap will be 0X0000000000000000000000001. This provides a fairly obvious mathematical
+ * property:
+ *   La < Lb <=> value(La) > (Lb)
+ *
+ * Each Set is a more classical bitmap. When a Level is added to a Set, the Level's bit is set in
+ * the Set's underlying value. When a Level is removed from a Set, the Level's bit is removed from
+ * the Set's underlying value. The rule is that each Level added to a Set must be less than any
+ * previously added Level. Likewise, each Level removed from a Set must be less than any
+ * remaining Level in the Set. Translated to math, the following is a pre-condition for adding a
+ * level L to a set S and a post-condition for removing a level L to a set S:
+ *   value(L) > value(S)
+ *
+ * In the interest of allowing the developer more flexibility and keeping these types simple, Set
+ * functions do not throw or return ErrorCodes, instead they return small enums. Note that
+ * operations always go through, even if the result is kInvalid.
+ */
+
+using ValueType = uint64_t;
+
+class Set;
+
+/**
+ * Level is a constexpr type that encodes an integer value into a bitmap
+ *
+ * This class is designed for use in non-type template parameters like so:
+ * template<Level kLevel>
+ * struct Foo {
+ *   void bar() {
+ *     gSet.add(kLevel);
+ *   }
+ * };
+ *
+ * Note that LT/LTE/GT/GTE operators are internally reversed because a low Level means a high
+ * ValueType.
+ */
+class Level {
+    friend class Set;
+
+public:
+    using IndexType = int32_t;
+
+    static constexpr IndexType kMinIndex = 0;
+    static constexpr IndexType kMaxIndex = sizeof(ValueType) * CHAR_BIT - 1;
+
+    explicit constexpr Level(IndexType index) : Level(maxValue() >> index) {}
+
+    constexpr Level prevLevel() const {
+        return Level(_value << 1);
+    }
+    constexpr Level nextLevel() const {
+        return Level(_value >> 1);
+    }
+
+    constexpr friend bool operator<(const Level& lhs, const Level& rhs) {
+        return lhs._value > rhs._value;
+    }
+
+    constexpr friend bool operator<=(const Level& lhs, const Level& rhs) {
+        return lhs._value >= rhs._value;
+    }
+
+    constexpr friend bool operator>(const Level& lhs, const Level& rhs) {
+        return lhs._value < rhs._value;
+    }
+
+    constexpr friend bool operator>=(const Level& lhs, const Level& rhs) {
+        return lhs._value <= rhs._value;
+    }
+
+    constexpr friend bool operator==(const Level& lhs, const Level& rhs) {
+        return lhs._value == rhs._value;
+    }
+
+    constexpr friend bool operator!=(const Level& lhs, const Level& rhs) {
+        return lhs._value != rhs._value;
+    }
+
+private:
+    static constexpr ValueType minValue() {
+        return ValueType{0x1} << kMinIndex;
+    }
+    static constexpr ValueType maxValue() {
+        return ValueType{0x1} << kMaxIndex;
+    }
+
+    explicit constexpr Level(ValueType value) : _value(value) {
+        invariantForConstexpr(_value >= minValue());
+        invariantForConstexpr(_value <= maxValue());
+    }
+
+    ValueType _value;
+};
+
+/**
+ * Set is a container type that adds or removes Levels
+ */
+class Set {
+public:
+    enum class AddResult {
+        kValidWasAbsent,
+        kInvalidWasAbsent,
+        kInvalidWasPresent,
+    };
+
+    friend StringData toString(AddResult result) {
+        switch (result) {
+            case AddResult::kValidWasAbsent: {
+                return "ValidWasAbsent"_sd;
+            } break;
+            case AddResult::kInvalidWasAbsent: {
+                return "InvalidWasAbsent"_sd;
+            } break;
+            case AddResult::kInvalidWasPresent: {
+                return "InvalidWasPresent"_sd;
+            } break;
+        }
+
+        MONGO_UNREACHABLE;
+    }
+
+    friend std::ostream& operator<<(std::ostream& os, const AddResult& result) {
+        return os << toString(result);
+    }
+
+    enum class RemoveResult {
+        kValidWasPresent,
+        kInvalidWasPresent,
+        kInvalidWasAbsent,
+    };
+
+    friend StringData toString(RemoveResult result) {
+        switch (result) {
+            case RemoveResult::kValidWasPresent: {
+                return "ValidWasPresent"_sd;
+            } break;
+            case RemoveResult::kInvalidWasPresent: {
+                return "InvalidWasPresent"_sd;
+            } break;
+            case RemoveResult::kInvalidWasAbsent: {
+                return "InvalidWasAbsent"_sd;
+            } break;
+        };
+
+        MONGO_UNREACHABLE;
+    }
+
+    friend std::ostream& operator<<(std::ostream& os, const RemoveResult& result) {
+        return os << toString(result);
+    }
+
+    /**
+     * Check if this set has a Level
+     */
+    bool has(const Level& level) const {
+        return _value & level._value;
+    }
+
+    /**
+     * Add a Level to this set
+     *
+     * There are three possible outcomes:
+     * - If level is already in the set, then return kInvalidWasPresent.
+     * - If level is not in the set and less than any level in the set, then add the level to the
+     *   set and return kInvalidWasAbsent.
+     * - If level is not in the set and greater than any level in the set, then add the level to the
+     *   set and return kValidWasAbsent.
+     */
+    auto add(const Level& level) {
+        if (_value & level._value) {
+            return AddResult::kInvalidWasPresent;
+        }
+
+        auto oldValue = _value;
+        _value |= level._value;
+
+        if (level._value < oldValue) {
+            return AddResult::kInvalidWasAbsent;
+        }
+
+        return AddResult::kValidWasAbsent;
+    }
+
+    /**
+     * Remove a Level from this set
+     *
+     * There are three possible outcomes:
+     * - If level is not in the set, then return kInvalidWasAbsent
+     * - If level is in the set and less than any other level in the set, then remove the level from
+     *   the set and return kInvalidWasPresent
+     * - If level is in the set and greater than any level in the set, then remove the level from
+     *   the set and return kValidWasPresent
+     */
+    auto remove(const Level& level) {
+        if (~_value & level._value) {
+            return RemoveResult::kInvalidWasAbsent;
+        }
+
+        _value &= ~level._value;
+
+        if (level._value < _value) {
+            return RemoveResult::kInvalidWasPresent;
+        }
+
+        return RemoveResult::kValidWasPresent;
+    }
+
+private:
+    ValueType _value = 0;
+};
+
+}  // namespace hierachical_acquisition_detail
+
+using HierarchicalAcquisitionSet = hierachical_acquisition_detail::Set;
+using HierarchicalAcquisitionLevel = hierachical_acquisition_detail::Level;
+
+}  // namespace mongo
diff --git a/src/mongo/util/hierarchical_acquisition_test.cpp b/src/mongo/util/hierarchical_acquisition_test.cpp
new file mode 100644
index 00000000000..97eed6c7cd5
--- /dev/null
+++ b/src/mongo/util/hierarchical_acquisition_test.cpp
@@ -0,0 +1,247 @@
+/**
+ *    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/platform/basic.h"
+
+#include "mongo/util/hierarchical_acquisition.h"
+
+#include <fmt/format.h>
+
+#include "mongo/platform/source_location.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+namespace {
+
+using namespace hierachical_acquisition_detail;
+
+struct Context {
+    friend std::string toString(Context context) {
+        using namespace fmt::literals;
+        return R"({{"level": {}, "sourceLocation": "{}"}})"_format(context.index,
+                                                                   context.loc.toString());
+    }
+
+    friend std::ostream& operator<<(std::ostream& os, const Context& context) {
+        return os << toString(context);
+    }
+
+    Level::IndexType index;
+    SourceLocationHolder loc;
+};
+
+#define MONGO_MAKE_CONTEXT(index)      \
+    Context {                          \
+        index, MONGO_SOURCE_LOCATION() \
+    }
+
+class HierarchicalAcquisitionTest : public unittest::Test {
+public:
+    void checkAdd(Level level, Set::AddResult expectedResult, Context context) {
+        ASSERT_EQ(_set.add(level), expectedResult) << context;
+        ASSERT_TRUE(_set.has(level)) << context;
+    }
+
+    void checkRemove(Level level, Set::RemoveResult expectedResult, Context context) {
+        if (expectedResult != Set::RemoveResult::kInvalidWasAbsent) {
+            ASSERT_TRUE(_set.has(level)) << context;
+        } else {
+            ASSERT_FALSE(_set.has(level)) << context;
+        }
+        ASSERT_EQ(_set.remove(level), expectedResult) << context;
+        ASSERT_FALSE(_set.has(level)) << context;
+    }
+
+    void resetSet() {
+        _set = Set();
+    }
+
+private:
+    Set _set;
+};
+
+TEST_F(HierarchicalAcquisitionTest, AcquireRelease) {
+    // This test performs the simplest idempotent set of successful operations on a single level L1:
+    // - add(L1) suceeds because nothing is set
+    // - remove(L1) suceeds because only L1 is set
+
+    for (auto i = Level::kMinIndex; i <= Level::kMaxIndex; ++i) {
+        Level level(i);
+
+        checkAdd(level, Set::AddResult::kValidWasAbsent, MONGO_MAKE_CONTEXT(i));
+        checkRemove(level, Set::RemoveResult::kValidWasPresent, MONGO_MAKE_CONTEXT(i));
+    };
+}
+
+TEST_F(HierarchicalAcquisitionTest, ReleaseAcquireAcquireReleaseRelease) {
+    // This test performs an exhaustive idempotent set of operations on a single Level L1:
+    // - remove(L1) fails because nothing is set
+    // - add(L1) suceeds because nothing is set
+    // - add(L1) fails because L1 is set
+    // - remove(L1) suceeds because L1 is set
+    // - remove(L1) fails because nothing is set
+
+    for (auto i = Level::kMinIndex; i <= Level::kMaxIndex; ++i) {
+        Level level(i);
+
+        // Removing an empty level fails
+        checkRemove(Level(i), Set::RemoveResult::kInvalidWasAbsent, MONGO_MAKE_CONTEXT(i));
+
+        // Adding an empty level succeeds
+        checkAdd(Level(i), Set::AddResult::kValidWasAbsent, MONGO_MAKE_CONTEXT(i));
+
+        // Adding a full level fails
+        checkAdd(Level(i), Set::AddResult::kInvalidWasPresent, MONGO_MAKE_CONTEXT(i));
+
+        // Removing a full level succeeds
+        checkRemove(Level(i), Set::RemoveResult::kValidWasPresent, MONGO_MAKE_CONTEXT(i));
+
+        // Removing an empty level again fails
+        checkRemove(Level(i), Set::RemoveResult::kInvalidWasAbsent, MONGO_MAKE_CONTEXT(i));
+    };
+}
+
+TEST_F(HierarchicalAcquisitionTest, DescendingAcquireLagRelease) {
+    // This test verifies that interleaved acquire releases fail as expected for two levels L1 and
+    // L2 where L1 > L2:
+    // - add(L2) suceeds because L1 > L2
+    // - remove(L1) fails because L1 > L2
+
+    auto testWithSkip = [&](Level::IndexType skip) {
+        // Set the first level
+        auto lag = Level::kMaxIndex;
+        checkAdd(Level(lag), Set::AddResult::kValidWasAbsent, MONGO_MAKE_CONTEXT(lag));
+
+        for (auto i = lag - skip; i >= Level::kMinIndex; lag = i, i -= skip) {
+            // Adding the current level succeeds
+            checkAdd(Level(i), Set::AddResult::kValidWasAbsent, MONGO_MAKE_CONTEXT(i));
+
+            // Removing the lag level fails
+            checkRemove(Level(lag), Set::RemoveResult::kInvalidWasPresent, MONGO_MAKE_CONTEXT(lag));
+        }
+
+        resetSet();
+    };
+
+    testWithSkip(1);
+    testWithSkip(2);
+    testWithSkip(3);
+    testWithSkip(8);
+}
+
+TEST_F(HierarchicalAcquisitionTest, AscendingAcquireReleaseLag) {
+    // This test verifies that interleaved acquire releases fail as expected for two levels L1 and
+    // L2 where L1 < L2:
+    // - add(L2) fails because L1 < L2
+    // - remove(L1) suceeds because L1 < L2
+
+    auto testWithSkip = [&](Level::IndexType skip) {
+        // Set the first level
+        auto lag = Level::kMinIndex;
+        checkAdd(Level(lag), Set::AddResult::kValidWasAbsent, MONGO_MAKE_CONTEXT(lag));
+
+        for (auto i = lag + skip; i <= Level::kMaxIndex; lag = i, i += skip) {
+            // Adding the current level fails
+            checkAdd(Level(i), Set::AddResult::kInvalidWasAbsent, MONGO_MAKE_CONTEXT(i));
+
+            // Removing the lag level succeeds
+            checkRemove(Level(lag), Set::RemoveResult::kValidWasPresent, MONGO_MAKE_CONTEXT(lag));
+        }
+
+        resetSet();
+    };
+
+    testWithSkip(1);
+    testWithSkip(2);
+    testWithSkip(3);
+    testWithSkip(8);
+}
+
+TEST_F(HierarchicalAcquisitionTest, DescendingAcquireAscendingRelease) {
+    // This test verifies that the expected set of sequential operations succeed:
+    // - add(L) for every L such that every previous L(n-1) > L
+    // - remove(L) for every L such that every previous L(n-1) < L
+
+    auto testWithSkip = [&](Level::IndexType skip) {
+        auto i = Level::kMaxIndex;
+        for (; i >= Level::kMinIndex; i -= skip) {
+            // Adding the current level succeeds
+            checkAdd(Level(i), Set::AddResult::kValidWasAbsent, MONGO_MAKE_CONTEXT(i));
+        };
+
+        for (i += skip; i <= Level::kMaxIndex; i += skip) {
+            // Removing the current level succeeds
+            checkRemove(Level(i), Set::RemoveResult::kValidWasPresent, MONGO_MAKE_CONTEXT(i));
+        };
+
+        resetSet();
+    };
+
+    testWithSkip(1);
+    testWithSkip(2);
+    testWithSkip(3);
+    testWithSkip(8);
+}
+
+TEST_F(HierarchicalAcquisitionTest, AscendingAcquireDescendingRelease) {
+    // This test verifies that the expected set of sequential operations fail:
+    // - add(L) for every L such that every previous L(n-1) < L
+    // - remove(L) for every L such that every previous L(n-1) > L
+
+    auto testWithSkip = [&](Level::IndexType skip) {
+        auto i = Level::kMinIndex;
+
+        // Set the first level
+        checkAdd(Level(i), Set::AddResult::kValidWasAbsent, MONGO_MAKE_CONTEXT(i));
+
+        for (i += skip; i <= (Level::kMaxIndex); i += skip) {
+            // Adding the current level fails
+            checkAdd(Level(i), Set::AddResult::kInvalidWasAbsent, MONGO_MAKE_CONTEXT(i));
+        };
+
+
+        for (i -= skip; i > Level::kMinIndex; i -= skip) {
+            // Removing the current level fails
+            checkRemove(Level(i), Set::RemoveResult::kInvalidWasPresent, MONGO_MAKE_CONTEXT(i));
+        };
+
+        // firstLevel is the only Level, so it succeeds
+        checkRemove(Level(i), Set::RemoveResult::kValidWasPresent, MONGO_MAKE_CONTEXT(i));
+
+        resetSet();
+    };
+
+    testWithSkip(1);
+    testWithSkip(2);
+    testWithSkip(3);
+    testWithSkip(8);
+}
+
+}  // namespace
+}  // namespace mongo
diff --git a/src/mongo/util/invariant.h b/src/mongo/util/invariant.h
index c4f0b0823aa..1a51354fa7b 100644
--- a/src/mongo/util/invariant.h
+++ b/src/mongo/util/invariant.h
@@ -111,4 +111,13 @@ inline void invariantWithContextAndLocation(
 
 #define dassert MONGO_dassert
 
+constexpr void invariantForConstexprThrower(bool val) {
+    enum { AbortException };
+    val ? 0 : throw AbortException;
+}
+
+constexpr void invariantForConstexpr(bool val) noexcept {
+    invariantForConstexprThrower(val);
+}
+
 }  // namespace mongo