SERVER-14425 Implement map with no allocation for the lock manager tracking structures

3 files changed, 441 insertions, 7 deletions

diff --git a/src/mongo/db/concurrency/SConscript b/src/mongo/db/concurrency/SConscript
index 1c492ee28eb..d448c7c0535 100644
--- a/src/mongo/db/concurrency/SConscript
+++ b/src/mongo/db/concurrency/SConscript
@@ -23,14 +23,11 @@ env.Library(
 env.CppUnitTest(
     target='lock_mgr_test',
     source=['d_concurrency_test.cpp',
+            'fast_map_noalloc_test.cpp',
             'lock_mgr_new_test.cpp',
-            'lock_state_test.cpp'
+            'lock_state_test.cpp',
     ],
     LIBDEPS=[
-        'lock_mgr',
-        '$BUILD_DIR/mongo/coredb',
-        '$BUILD_DIR/mongo/coreserver',
-        '$BUILD_DIR/mongo/serveronly'
-    ],
-    NO_CRUTCH = True
+        'lock_mgr'
+    ]
 )
diff --git a/src/mongo/db/concurrency/fast_map_noalloc.h b/src/mongo/db/concurrency/fast_map_noalloc.h
new file mode 100644
index 00000000000..5c9c275a5da
--- /dev/null
+++ b/src/mongo/db/concurrency/fast_map_noalloc.h
@@ -0,0 +1,275 @@
+/**
+ *    Copyright (C) 2014 MongoDB Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    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
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    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 GNU Affero General 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 "mongo/platform/unordered_map.h"
+#include "mongo/util/assert_util.h"
+
+namespace mongo {
+    
+    /**
+     * NOTE: This structure should not be used for anything other than the Lock Manager.
+     *
+     * This is a simple implementation of an unordered associative array with minimal
+     * functionality, used by the lock manager. It keeps a small number of memory entries to store
+     * values, in order to avoid memory allocations, which dominate the cost of the lock manager
+     * calls by a wide margin.
+     *
+     * This class is not thread-safe.
+     */
+    template <class KeyType, class ValueType, int PreallocCount>
+    class FastMapNoAlloc {
+    public:
+
+        /**
+         * Forward-only iterator. Does not synchronize with the underlying collection in any way.
+         * In other words, do not modify the collection while there is an open iterator on it.
+         */
+        template<class MapType, class IteratorValueType>
+        class IteratorImpl {
+        public:
+
+            IteratorImpl(const IteratorImpl& other)
+                : _map(other._map),
+                  _idx(other._idx) {
+
+            }
+
+
+            //
+            // Operators
+            //
+
+            bool operator!() const {
+                return finished();
+            }
+
+            IteratorValueType& operator*() const {
+                return *objAddr();
+            }
+
+            IteratorValueType* operator->() const {
+                return objAddr();
+            }
+
+
+            //
+            // Other methods
+            //
+
+            /**
+             * Returns whether the iterator has been exhausted through calls to next. This value
+             * can be used to determine whether a previous call to find ahs found something.
+             */
+            bool finished() const {
+                return (MONGO_likely(_idx == PreallocCount));
+            }
+
+            /**
+             * Returns the address of the object at the current position. Cannot be called with an
+             * uninitialized iterator, or iterator which has reached the end.
+             */
+            IteratorValueType* objAddr() const {
+                invariant(!finished());
+
+                return &_map._fastAccess[_idx].value;
+            }
+
+            /**
+             * Returns the key of the value at the current position. Cannot be called with an
+             * uninitialized iterator or iterator which has reached the end.
+             */
+            const KeyType& key() const {
+                invariant(!finished());
+
+                return _map._fastAccess[_idx].key;
+            }
+
+            /**
+             * Advances the iterator to the next entry. No particular order of iteration is
+             * guaranteed.
+             */
+            void next() {
+                invariant(!finished());
+
+                while (++_idx < PreallocCount) {
+                    if (_map._fastAccess[_idx].inUse) {
+                        return;
+                    }
+                }
+            }
+
+            /**
+             * Removes the element at the current position and moves the iterator to the next,
+             * which might be the last entry on the map.
+             */
+            void remove() {
+                invariant(!finished());
+                invariant(_map._fastAccess[_idx].inUse);
+
+                _map._fastAccess[_idx].inUse = false;
+                _map._fastAccessUsedSize--;
+
+                next();
+            }
+
+
+        private:
+
+            friend class FastMapNoAlloc<KeyType, ValueType, PreallocCount>;
+
+            // Used for iteration of the complete map
+            IteratorImpl(MapType& map)
+                : _map(map),
+                  _idx(-1) {
+
+                next();
+            }
+
+            // Used for iterator starting at a position
+            IteratorImpl(MapType& map, int idx)
+                : _map(map),
+                  _idx(idx) {
+
+                invariant(_idx >= 0);
+            }
+
+            // Used for iteration starting at a particular key
+            IteratorImpl(MapType& map, const KeyType& key)
+                : _map(map),
+                  _idx(0) {
+
+                while (_idx < PreallocCount) {
+                    if (_map._fastAccess[_idx].inUse && (_map._fastAccess[_idx].key == key)) {
+                        return;
+                    }
+
+                    ++_idx;
+                }
+            }
+
+
+            // The map being iterated on
+            MapType& _map;
+
+            // Index to the current entry being iterated
+            int _idx;
+        };
+
+
+        typedef IteratorImpl<FastMapNoAlloc<KeyType, ValueType, PreallocCount>,
+                             ValueType> Iterator;
+
+        typedef IteratorImpl<const FastMapNoAlloc<KeyType, ValueType, PreallocCount>,
+                             const ValueType> ConstIterator;
+
+
+        FastMapNoAlloc() : _fastAccess(),
+                           _fastAccessUsedSize(0) { }
+
+        /**
+         * Inserts the specified entry in the map and returns a reference to the memory for the
+         * entry just inserted.
+         */
+        Iterator insert(const KeyType& key) {
+            // Find the first unused slot. This could probably be even further optimized by adding
+            // a field pointing to the first unused location.
+            int idx = 0;
+            for (; _fastAccess[idx].inUse; idx++);
+
+            invariant(idx < PreallocCount);
+
+            _fastAccess[idx].inUse = true;
+            _fastAccess[idx].key = key;
+            _fastAccessUsedSize++;
+
+            return Iterator(*this, idx);
+        }
+
+        /**
+         * Returns an iterator to the first element in the map.
+         */
+        Iterator begin() {
+            return Iterator(*this);
+        }
+
+        ConstIterator begin() const {
+            return ConstIterator(*this);
+        }
+
+        /**
+         * Returns an iterator pointing to the first position, which has entry with the specified
+         * key. Before dereferencing the returned iterator, it should be checked for validity using
+         * the finished() method or the ! operator. If no element was found, finished() will return
+         * false.
+         * 
+         * While it is allowed to call next() on the returned iterator, this is not very useful,
+         * because the container is not ordered.
+         */
+        Iterator find(const KeyType& key) {
+            return Iterator(*this, key);
+        }
+
+        ConstIterator find(const KeyType& key) const {
+            return ConstIterator(*this, key);
+        }
+
+        int size() const { return _fastAccessUsedSize; }
+        bool empty() const { return (_fastAccessUsedSize == 0); }
+
+    private:
+
+        // Empty and very large maps do not make sense since there will be no performance gain, so
+        // disallow them.
+        BOOST_STATIC_ASSERT(PreallocCount > 0);
+        BOOST_STATIC_ASSERT(PreallocCount < 32);
+
+        // Iterator accesses the map directly
+        friend class IteratorImpl<FastMapNoAlloc<KeyType, ValueType, PreallocCount>,
+                                  ValueType>;
+
+        friend class IteratorImpl<const FastMapNoAlloc<KeyType, ValueType, PreallocCount>,
+                                  const ValueType>;
+
+
+        struct PreallocEntry {
+            PreallocEntry() : inUse(false) { }
+
+            bool inUse;
+
+            KeyType key;
+            ValueType value;
+        };
+
+        // Pre-allocated memory for entries
+        PreallocEntry _fastAccess[PreallocCount];
+        int _fastAccessUsedSize;
+    };
+
+} // namespace mongo
diff --git a/src/mongo/db/concurrency/fast_map_noalloc_test.cpp b/src/mongo/db/concurrency/fast_map_noalloc_test.cpp
new file mode 100644
index 00000000000..84543f3fc03
--- /dev/null
+++ b/src/mongo/db/concurrency/fast_map_noalloc_test.cpp
@@ -0,0 +1,162 @@
+/**
+ *    Copyright (C) 2014 MongoDB Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    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
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    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 GNU Affero General 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 <boost/lexical_cast.hpp>
+#include <string>
+
+#include "mongo/db/concurrency/fast_map_noalloc.h"
+#include "mongo/db/concurrency/resource_id.h"
+#include "mongo/unittest/unittest.h"
+
+
+namespace mongo {
+
+    struct TestStruct {
+
+        void initNew(int newId, const std::string& newValue) {
+            id = newId;
+            value = newValue;
+        }
+
+        int id;
+        std::string value;
+    };
+
+    typedef class FastMapNoAlloc<ResourceId, TestStruct, 6> TestFastMapNoAlloc;
+
+
+    TEST(FastMapNoAlloc, Empty) {
+        TestFastMapNoAlloc map;
+        ASSERT(map.empty());
+
+        TestFastMapNoAlloc::Iterator it = map.begin();
+        ASSERT(it.finished());
+    }
+
+    TEST(FastMapNoAlloc, NotEmpty) {
+        TestFastMapNoAlloc map;
+
+        map.insert(ResourceId(RESOURCE_DOCUMENT, 1))->initNew(101, "Item101");
+        map.insert(ResourceId(RESOURCE_DOCUMENT, 2))->initNew(102, "Item102");
+        ASSERT(!map.empty());
+
+        TestFastMapNoAlloc::Iterator it = map.begin();
+        ASSERT(!it.finished());
+        ASSERT(!!it);
+
+        ASSERT(it->id == 101);
+        ASSERT(it->value == "Item101");
+
+        it.next();
+        ASSERT(!it.finished());
+        ASSERT(!!it);
+
+        ASSERT(it->id == 102);
+        ASSERT(it->value == "Item102");
+
+        // We are at the last element
+        it.next();
+        ASSERT(it.finished());
+        ASSERT(!it);
+    }
+
+    TEST(FastMapNoAlloc, FindNonExisting) {
+        TestFastMapNoAlloc map;
+
+        ASSERT(!map.find(ResourceId(RESOURCE_DOCUMENT, 0)));
+    }
+
+    TEST(FastMapNoAlloc, FindAndRemove) {
+        TestFastMapNoAlloc map;
+
+        for (int i = 0; i < 6; i++) {
+            map.insert(ResourceId(RESOURCE_DOCUMENT, i))->initNew(
+                                                i, "Item" + boost::lexical_cast<std::string>(i));
+        }
+
+        for (int i = 0; i < 6; i++) {
+            ASSERT(!map.find(ResourceId(RESOURCE_DOCUMENT, i)).finished());
+
+            ASSERT_EQUALS(i, map.find(ResourceId(RESOURCE_DOCUMENT, i))->id);
+
+            ASSERT_EQUALS("Item" + boost::lexical_cast<std::string>(i),
+                          map.find(ResourceId(RESOURCE_DOCUMENT, i))->value);
+        }
+
+        // Remove a middle entry
+        map.find(ResourceId(RESOURCE_DOCUMENT, 2)).remove();
+        ASSERT(!map.find(ResourceId(RESOURCE_DOCUMENT, 2)));
+
+        // Remove entry after first
+        map.find(ResourceId(RESOURCE_DOCUMENT, 1)).remove();
+        ASSERT(!map.find(ResourceId(RESOURCE_DOCUMENT, 1)));
+
+        // Remove entry before last
+        map.find(ResourceId(RESOURCE_DOCUMENT, 4)).remove();
+        ASSERT(!map.find(ResourceId(RESOURCE_DOCUMENT, 4)));
+
+        // Remove first entry
+        map.find(ResourceId(RESOURCE_DOCUMENT, 0)).remove();
+        ASSERT(!map.find(ResourceId(RESOURCE_DOCUMENT, 0)));
+
+        // Remove last entry
+        map.find(ResourceId(RESOURCE_DOCUMENT, 5)).remove();
+        ASSERT(!map.find(ResourceId(RESOURCE_DOCUMENT, 5)));
+
+        // Remove final entry
+        map.find(ResourceId(RESOURCE_DOCUMENT, 3)).remove();
+        ASSERT(!map.find(ResourceId(RESOURCE_DOCUMENT, 3)));
+    }
+
+    TEST(FastMapNoAlloc, RemoveAll) {
+        TestFastMapNoAlloc map;
+        std::unordered_map<ResourceId, TestStruct> checkMap;
+
+        for (int i = 1; i <= 6; i++) {
+            map.insert(ResourceId(RESOURCE_DOCUMENT, i))->initNew(
+                                                i, "Item" + boost::lexical_cast<std::string>(i));
+
+            checkMap[ResourceId(RESOURCE_DOCUMENT, i)].initNew(
+                                                i, "Item" + boost::lexical_cast<std::string>(i));
+        }
+
+        TestFastMapNoAlloc::Iterator it = map.begin();
+        while (!it.finished()) {
+            ASSERT_EQUALS(it->id, checkMap[it.key()].id);
+            ASSERT_EQUALS(
+                "Item" + boost::lexical_cast<std::string>(it->id), checkMap[it.key()].value);
+
+            checkMap.erase(it.key());
+            it.remove();
+        }
+
+        ASSERT(map.empty());
+        ASSERT(checkMap.empty());
+    }
+
+} // namespace mongo