quickstep-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hbdeshm...@apache.org
Subject [16/50] [abbrv] incubator-quickstep git commit: Transaction Part 4: LockManager, CycleDetector and DeadLockDetector. (#187)
Date Wed, 08 Jun 2016 13:21:16 GMT
Transaction Part 4: LockManager, CycleDetector and DeadLockDetector. (#187)

Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/bbaff7a2
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/bbaff7a2
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/bbaff7a2

Branch: refs/heads/query-manager-used-in-foreman
Commit: bbaff7a2aa84b0792a33ca652da701c1b3498008
Parents: a3889a3
Author: Hakan Memisoglu <hakanmemisoglu@gmail.com>
Authored: Wed May 4 23:30:51 2016 -0500
Committer: Zuyu ZHANG <zuyu@users.noreply.github.com>
Committed: Wed May 4 21:30:51 2016 -0700

----------------------------------------------------------------------
 transaction/AccessMode.hpp                      |  76 +++++-
 transaction/CMakeLists.txt                      |  59 ++++-
 transaction/CycleDetector.cpp                   | 120 ++++++++++
 transaction/CycleDetector.hpp                   |  83 +++++++
 transaction/DeadLockDetector.cpp                | 177 ++++++++++++++
 transaction/DeadLockDetector.hpp                | 156 ++++++++++++
 transaction/DirectedGraph.hpp                   |  56 ++---
 transaction/LockManager.cpp                     | 237 +++++++++++++++++++
 transaction/LockManager.hpp                     | 128 ++++++++++
 transaction/LockTable.cpp                       |  22 +-
 transaction/LockTable.hpp                       |  36 +--
 transaction/ResourceId.hpp                      |   9 +-
 transaction/StronglyConnectedComponents.cpp     |   1 -
 transaction/Transaction.cpp                     |  48 ----
 transaction/TransactionTable.cpp                |   8 +-
 transaction/TransactionTable.hpp                |  11 +-
 transaction/tests/AccessMode_unittest.cpp       |  12 +-
 transaction/tests/CycleDetector_unittest.cpp    | 157 ++++++++++++
 transaction/tests/DeadLockDetector_unittest.cpp |  96 ++++++++
 transaction/tests/DirectedGraph_unittest.cpp    | 113 +++++----
 transaction/tests/LockRequest_unittest.cpp      |   4 +-
 transaction/tests/LockTable_unittest.cpp        |  63 ++---
 transaction/tests/Lock_unittest.cpp             |  13 +-
 .../StronglyConnectedComponents_unittest.cpp    |  15 +-
 transaction/tests/TransactionTable_unittest.cpp | 102 ++++----
 25 files changed, 1512 insertions(+), 290 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/AccessMode.hpp
----------------------------------------------------------------------
diff --git a/transaction/AccessMode.hpp b/transaction/AccessMode.hpp
index 34ace36..bb06689 100644
--- a/transaction/AccessMode.hpp
+++ b/transaction/AccessMode.hpp
@@ -32,12 +32,12 @@ namespace transaction {
  * @brief Represents mode type. Possible options are NL, IS, IX, S, SIX, X.
  **/
 enum class AccessModeType : std::uint8_t {
-  kNoLock = 0,
-  kIsLock,
-  kIxLock,
-  kSLock,
-  kSixLock,
-  kXLock,
+  kNoLockMode = 0,
+  kIsLockMode,
+  kIxLockMode,
+  kSLockMode,
+  kSixLockMode,
+  kXLockMode,
   kNumAccessModeTypes,
 };
 
@@ -55,6 +55,60 @@ class AccessMode {
       : access_mode_(access_mode) {}
 
   /**
+   * @brief Factory method for NoLockMode.
+   *
+   * @return NoLockMode instance.
+   **/
+  static AccessMode NoLockMode() {
+    return AccessMode(AccessModeType::kNoLockMode);
+  }
+
+  /**
+   * @brief Factory method for IsLockMode.
+   *
+   * @return IsLockMode instance.
+   **/
+  static AccessMode IsLockMode() {
+    return AccessMode(AccessModeType::kIsLockMode);
+  }
+
+  /**
+   * @brief Factory method for IxLockMode.
+   *
+   * @return IxLockMode instance.
+   **/
+  static AccessMode IxLockMode() {
+    return AccessMode(AccessModeType::kIxLockMode);
+  }
+
+  /**
+   * @brief Factory method for SixLockMode.
+   *
+   * @return SixLockMode instance.
+   **/
+  static AccessMode SixLockMode() {
+    return AccessMode(AccessModeType::kSixLockMode);
+  }
+
+  /**
+   * @brief Factory method for SLockMode.
+   *
+   * @return SLockMode instance.
+   **/
+  static AccessMode SLockMode() {
+    return AccessMode(AccessModeType::kSLockMode);
+  }
+
+  /**
+   * @brief Factory method for XLockMode.
+   *
+   * @return XLockMode instance.
+   **/
+  static AccessMode XLockMode() {
+    return AccessMode(AccessModeType::kXLockMode);
+  }
+
+  /**
    * @brief Checks whether this access mode is compatible with the other.
    *
    * @param other Other access mode that will be checked against to this one.
@@ -74,7 +128,7 @@ class AccessMode {
    * @return True if it is IS mode, false otherwise.
    **/
   inline bool isIntentionShareLock() const {
-    return access_mode_ == AccessModeType::kIsLock;
+    return access_mode_ == AccessModeType::kIsLockMode;
   }
 
   /**
@@ -83,7 +137,7 @@ class AccessMode {
    * @return True if it is IX mode, false otherwise.
    **/
   inline bool isIntentionExclusiveLock() const {
-    return access_mode_ == AccessModeType::kIxLock;
+    return access_mode_ == AccessModeType::kIxLockMode;
   }
 
   /**
@@ -92,7 +146,7 @@ class AccessMode {
    * @return True if it is SIX mode, false otherwise.
    **/
   inline bool isShareAndIntentionExclusiveLock() const {
-    return access_mode_ == AccessModeType::kSixLock;
+    return access_mode_ == AccessModeType::kSixLockMode;
   }
 
   /**
@@ -101,7 +155,7 @@ class AccessMode {
    * @return True if it is S mode, false otherwise.
    **/
   inline bool isShareLock() const {
-    return access_mode_ == AccessModeType::kSLock;
+    return access_mode_ == AccessModeType::kSLockMode;
   }
 
   /**
@@ -110,7 +164,7 @@ class AccessMode {
    * @return True if it is X mode, false otherwise.
    **/
   inline bool isExclusiveLock() const {
-    return access_mode_ == AccessModeType::kXLock;
+    return access_mode_ == AccessModeType::kXLockMode;
   }
 
   /**

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/transaction/CMakeLists.txt b/transaction/CMakeLists.txt
index 05fc96a..c6c87b6 100644
--- a/transaction/CMakeLists.txt
+++ b/transaction/CMakeLists.txt
@@ -16,12 +16,21 @@
 add_library(quickstep_transaction_AccessMode
             AccessMode.cpp
             AccessMode.hpp)
+add_library(quickstep_transaction_CycleDetector
+            CycleDetector.cpp
+            CycleDetector.hpp)
+add_library(quickstep_transaction_DeadLockDetector
+            DeadLockDetector.cpp
+            DeadLockDetector.cpp)
 add_library(quickstep_transaction_DirectedGraph
             ../empty_src.cpp
             DirectedGraph.hpp)
 add_library(quickstep_transaction_Lock
             ../empty_src.cpp
             Lock.hpp)
+add_library(quickstep_transaction_LockManager
+            LockManager.hpp
+            LockManager.cpp)
 add_library(quickstep_transaction_LockRequest
             ../empty_src.cpp
             LockRequest.hpp)
@@ -40,7 +49,17 @@ add_library(quickstep_transaction_Transaction
 add_library(quickstep_transaction_TransactionTable
             TransactionTable.cpp
             TransactionTable.hpp)
-          
+
+target_link_libraries(quickstep_transaction_CycleDetector
+                      quickstep_transaction_DirectedGraph
+                      quickstep_transaction_StronglyConnectedComponents
+                      quickstep_utility_Macros)
+target_link_libraries(quickstep_transaction_DeadLockDetector
+                      glog
+                      quickstep_transaction_CycleDetector
+                      quickstep_transaction_DirectedGraph
+                      quickstep_transaction_LockTable
+                      quickstep_transaction_Transaction)
 target_link_libraries(quickstep_transaction_DirectedGraph
                       glog
                       quickstep_transaction_Transaction
@@ -48,6 +67,18 @@ target_link_libraries(quickstep_transaction_DirectedGraph
 target_link_libraries(quickstep_transaction_Lock
                       quickstep_transaction_AccessMode
                       quickstep_transaction_ResourceId)
+target_link_libraries(quickstep_transaction_LockManager
+                      gflags_nothreads-static
+                      glog
+                      quickstep_utility_ThreadSafeQueue
+                      quickstep_threading_Thread
+                      quickstep_transaction_AccessMode
+                      quickstep_transaction_DeadLockDetector
+                      quickstep_transaction_LockRequest
+                      quickstep_transaction_LockTable
+                      quickstep_transaction_ResourceId
+                      quickstep_transaction_Transaction
+                      quickstep_transaction_TransactionTable)
 target_link_libraries(quickstep_transaction_LockRequest
                       quickstep_transaction_AccessMode
                       quickstep_transaction_ResourceId
@@ -80,8 +111,11 @@ add_library(quickstep_transaction
             TransactionModule.hpp)
 target_link_libraries(quickstep_transaction
                       quickstep_transaction_AccessMode
+                      quickstep_transaction_CycleDetector
+                      quickstep_transaction_DeadLockDetector
                       quickstep_transaction_DirectedGraph
                       quickstep_transaction_Lock
+                      quickstep_transaction_LockManager
                       quickstep_transaction_LockRequest
                       quickstep_transaction_LockTable
                       quickstep_transaction_ResourceId
@@ -97,6 +131,29 @@ target_link_libraries(AccessMode_unittest
                       quickstep_transaction_AccessMode)
 add_test(AccessMode_unittest AccessMode_unittest)
 
+add_executable(CycleDetector_unittest
+               "${CMAKE_CURRENT_SOURCE_DIR}/tests/CycleDetector_unittest.cpp")
+target_link_libraries(CycleDetector_unittest
+                      gtest
+                      gtest_main
+                      quickstep_transaction_CycleDetector
+                      quickstep_transaction_DirectedGraph
+                      quickstep_transaction_StronglyConnectedComponents)
+add_test(CycleDetector_unittest CycleDetector_unittest)
+
+add_executable(DeadLockDetector_unittest
+  "${CMAKE_CURRENT_SOURCE_DIR}/tests/DeadLockDetector_unittest.cpp")
+target_link_libraries(DeadLockDetector_unittest
+                      gtest
+                      gtest_main
+                      quickstep_threading_Thread
+                      quickstep_transaction_AccessMode
+                      quickstep_transaction_DeadLockDetector
+                      quickstep_transaction_LockTable
+                      quickstep_transaction_ResourceId
+                      quickstep_transaction_Transaction)
+add_test(DeadLockDetector_unittest DeadLockDetector_unittest)
+
 add_executable(DirectedGraph_unittest
                "${CMAKE_CURRENT_SOURCE_DIR}/tests/DirectedGraph_unittest.cpp")
 target_link_libraries(DirectedGraph_unittest

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/CycleDetector.cpp
----------------------------------------------------------------------
diff --git a/transaction/CycleDetector.cpp b/transaction/CycleDetector.cpp
new file mode 100644
index 0000000..b12897f
--- /dev/null
+++ b/transaction/CycleDetector.cpp
@@ -0,0 +1,120 @@
+/**
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
+ *
+ *   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 "transaction/CycleDetector.hpp"
+
+#include <cstdint>
+#include <memory>
+#include <stack>
+#include <unordered_map>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+#include "transaction/DirectedGraph.hpp"
+#include "transaction/StronglyConnectedComponents.hpp"
+
+namespace quickstep {
+namespace transaction {
+
+CycleDetector::CycleDetector(DirectedGraph *wait_for_graph)
+    : wait_for_graph_(wait_for_graph),
+      strongly_connected_components_(
+          std::make_unique<StronglyConnectedComponents>(*wait_for_graph)) {
+}
+
+std::vector<DirectedGraph::node_id>
+CycleDetector::chooseVictimsToBreakCycle() const {
+  std::vector<DirectedGraph::node_id> nodes_to_kill;
+  const std::unordered_map<std::uint64_t, std::vector<DirectedGraph::node_id>>
+      component_mapping = strongly_connected_components_->getComponentMapping();
+  for (const auto &entry : component_mapping) {
+    // One node means no cycle.
+    if (entry.second.size() == 1) {
+      continue;
+    }
+    const std::vector<DirectedGraph::node_id> nodes =
+        chooseVictimsInComponent(entry.second);
+    nodes_to_kill.insert(nodes_to_kill.end(), nodes.begin(), nodes.end());
+  }
+  return nodes_to_kill;
+}
+
+std::vector<DirectedGraph::node_id> CycleDetector::chooseVictimsInComponent(
+    const std::vector<DirectedGraph::node_id> &nodes) const {
+  std::vector<DirectedGraph::node_id> targets;
+  // Convert it to set to ensure defensively that the elements are unique.
+  std::unordered_set<DirectedGraph::node_id> nodes_set(nodes.begin(),
+                                                       nodes.end());
+
+  while (true) {
+    if (!hasCycle(nodes_set)) {
+      break;
+    }
+    // Connected component still has a cycle, therefore choose a
+    // victim and keep trying to remove nodes until there is no cycle.
+    const DirectedGraph::node_id victim = chooseVictim(nodes_set);
+    // Remove the victim node from the connected component.
+    nodes_set.erase(victim);
+    // Removed node is a victim now.
+    targets.push_back(victim);
+  }
+  return targets;
+}
+
+bool CycleDetector::hasCycle(
+    const std::unordered_set<DirectedGraph::node_id> &nodes) const {
+  // Keeps track of the nodes the algorithms visited.
+  std::unordered_set<DirectedGraph::node_id> visited;
+  for (const DirectedGraph::node_id node_id : nodes) {
+    // If it is visited, then pass to the next one.
+    if (visited.count(node_id) == 1) {
+      continue;
+    }
+    // Save the backtracking information.
+    std::stack<DirectedGraph::node_id> to_visit;
+    // Mark this id as "to be visited".
+    to_visit.push(node_id);
+    // Start to visit nodes until it is done.
+    while (!to_visit.empty()) {
+      const DirectedGraph::node_id current_node = to_visit.top();
+      to_visit.pop();
+      // Mark the node coming from stack as "visited".
+      visited.insert(current_node);
+      // For all adjacent nodes of this "visited" node,
+      const std::vector<DirectedGraph::node_id> adjacents
+          = wait_for_graph_->getAdjacentNodes(current_node);
+      for (const DirectedGraph::node_id adjacent : adjacents) {
+        if (visited.count(adjacent) == 1) {
+          // If this adjacent node is a node we already visited, then
+          // there is a cycle.
+          return true;
+        } else if (nodes.count(adjacent) == 1 && visited.count(adjacent) == 0) {
+          // Otherwise, if it is a node that we did not visit before
+          // mark this nodes as "to be visited".
+          to_visit.push(adjacent);
+        }
+      }
+    }
+  }
+  // If we have already visited all nodes and could not find a cycle,
+  // then we should return "no cycle" result.
+  return false;
+}
+
+}  // namespace transaction
+}  // namespace quickstep

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/CycleDetector.hpp
----------------------------------------------------------------------
diff --git a/transaction/CycleDetector.hpp b/transaction/CycleDetector.hpp
new file mode 100644
index 0000000..6865e2d
--- /dev/null
+++ b/transaction/CycleDetector.hpp
@@ -0,0 +1,83 @@
+/**
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
+ *
+ *   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.
+ **/
+
+#ifndef QUICKSTEP_TRANSACTION_CYCLE_DETECTOR_HPP_
+#define QUICKSTEP_TRANSACTION_CYCLE_DETECTOR_HPP_
+
+#include <memory>
+#include <unordered_set>
+#include <vector>
+
+#include "transaction/DirectedGraph.hpp"
+#include "transaction/StronglyConnectedComponents.hpp"
+#include "utility/Macros.hpp"
+
+namespace quickstep {
+namespace transaction {
+
+/** \addtogroup Transaction
+ *  @{
+ */
+
+/**
+ * @brief Class for running cycle detection algorithm on directed graph.
+ */
+class CycleDetector {
+ public:
+  /**
+   * @brief Constructor for DirectedGraph.
+   *
+   * @param wait_for_graph Pointer to a directed wait-for graph.
+   */
+  explicit CycleDetector(DirectedGraph *wait_for_graph);
+
+  /**
+   * @brief Calculate which nodes should be killed to eliminate all cycles
+   *        in the graph.
+   *
+   * @return Vector of node ids that should be killed to break all cycles.
+   */
+  std::vector<DirectedGraph::node_id> chooseVictimsToBreakCycle() const;
+
+ private:
+  std::vector<DirectedGraph::node_id> chooseVictimsInComponent(
+      const std::vector<DirectedGraph::node_id> &nodes) const;
+
+  inline DirectedGraph::node_id chooseVictim(
+      const std::unordered_set<DirectedGraph::node_id> &nodes_set) const {
+    // TODO(Hakan): This is very inefficient scheme, however in the
+    //              future, we can use the transaction's priority
+    //              as the victim selection parameter.
+    return *(nodes_set.begin());
+  }
+
+  // Checks whether the nodes in the set make a cycle.
+  bool hasCycle(const std::unordered_set<DirectedGraph::node_id> &within) const;
+
+  DirectedGraph *wait_for_graph_;
+
+  std::unique_ptr<StronglyConnectedComponents> strongly_connected_components_;
+
+  DISALLOW_COPY_AND_ASSIGN(CycleDetector);
+};
+
+/** @} */
+
+}  // namespace transaction
+}  // namespace quickstep
+
+#endif  // QUICKSTEP_TRANSACTION_CYCLE_DETECTOR_HPP_

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/DeadLockDetector.cpp
----------------------------------------------------------------------
diff --git a/transaction/DeadLockDetector.cpp b/transaction/DeadLockDetector.cpp
new file mode 100644
index 0000000..26ab115
--- /dev/null
+++ b/transaction/DeadLockDetector.cpp
@@ -0,0 +1,177 @@
+/**
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
+ *
+ *   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 "transaction/DeadLockDetector.hpp"
+
+#include <algorithm>
+#include <atomic>
+#include <chrono>
+#include <memory>
+#include <thread>  // NOLINT(build/c++11)
+#include <utility>
+#include <vector>
+
+#include "transaction/CycleDetector.hpp"
+#include "transaction/DirectedGraph.hpp"
+#include "transaction/LockTable.hpp"
+#include "transaction/Transaction.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+namespace transaction {
+
+constexpr std::int64_t DeadLockDetector::kSleepDurationInSeconds;
+
+DeadLockDetector::DeadLockDetector(LockTable *lock_table,
+                                   std::atomic<DeadLockDetectorStatus> *status,
+                                   std::vector<DirectedGraph::node_id> *victims)
+    : tid_node_mapping_(std::make_unique<transaction_id_node_map>()),
+      lock_table_(lock_table),
+      status_(status),
+      victims_(victims) {
+}
+
+void DeadLockDetector::run() {
+  while (true) {
+    if (status_->load() == DeadLockDetectorStatus::kQuit) {
+      // DeadLockDetector should stop.
+      return;
+    }
+    while (status_->load() == DeadLockDetectorStatus::kDone) {
+      // LockTable has not process the previous batch yet.
+    }
+
+    // TODO(Hakan): Implement logging mechanism for deadlock detection
+    //              start and end times.
+    std::vector<DirectedGraph::node_id> victim_new_batch = getAllVictims();
+
+    // Swap new batch with old batch to make LockTable to see new victims.
+    std::swap(victim_new_batch, *victims_);
+
+    // Signal LockTable that new batch is ready.
+    status_->store(DeadLockDetectorStatus::kDone);
+
+    // DeadLockDetector should run once in a predefined interval.
+    std::this_thread::sleep_for(
+        std::chrono::seconds(kSleepDurationInSeconds));
+  }
+}
+
+void DeadLockDetector::addPendingInfo(const transaction_id pending,
+                                      const transaction_id owner) {
+  const DirectedGraph::node_id pending_node_id = getNodeId(pending);
+  const DirectedGraph::node_id owner_node_id = getNodeId(owner);
+
+  // TODO(Hakan): Check first whether link is already created. Use checked
+  //              version for adding an edge.
+  wait_for_graph_->addEdgeUnchecked(pending_node_id, owner_node_id);
+}
+
+void DeadLockDetector::deletePendingInfo(const transaction_id pending,
+                                         const transaction_id owner) {
+  LOG(FATAL) << "Not implemented";
+}
+
+bool DeadLockDetector::isDependent(const transaction_id pending,
+                                   const transaction_id owner) const {
+  LOG(FATAL) << "Not implemented";
+}
+
+std::vector<transaction_id>
+DeadLockDetector::getAllDependents(const transaction_id owner) const {
+  LOG(FATAL) << "Not implemented";
+}
+
+std::vector<transaction_id>
+DeadLockDetector::getAllDependees(transaction_id pending) {
+  const DirectedGraph::node_id pending_node_id = getNodeId(pending);
+  const std::vector<DirectedGraph::node_id> nodes
+      = wait_for_graph_->getAdjacentNodes(pending_node_id);
+  std::vector<transaction_id> transactions;
+  transactions.reserve(nodes.size());
+  for (const DirectedGraph::node_id node_id : nodes) {
+    const transaction_id tid = wait_for_graph_->getDataFromNode(node_id);
+    transactions.push_back(tid);
+  }
+  return transactions;
+}
+
+DirectedGraph::node_id DeadLockDetector::getNodeId(const transaction_id tid) {
+  DirectedGraph::node_id node_id;
+  if (tid_node_mapping_->count(tid) == 0) {
+    // If it is not created, create it.
+    node_id = addNode(tid);
+  } else {
+    // Otherwise find it in the map.
+    node_id = (*tid_node_mapping_)[tid];
+  }
+  return node_id;
+}
+
+
+DirectedGraph::node_id DeadLockDetector::addNode(const transaction_id tid) {
+  const DirectedGraph::node_id node_id =
+      wait_for_graph_->addNodeUnchecked(tid);
+  tid_node_mapping_->emplace(tid, node_id);
+  return node_id;
+}
+
+std::vector<transaction_id> DeadLockDetector::getAllVictims()  {
+  std::vector<transaction_id> result_victims;
+  wait_for_graph_.reset(new DirectedGraph());
+
+  // Critical region on LockTable starts here.
+  lock_table_->latchShared();
+  for (const auto &lock_control_block : *lock_table_) {
+    const LockTable::lock_own_list &own_list = lock_control_block.second.first;
+    const LockTable::lock_pending_list &pending_list =
+        lock_control_block.second.second;
+
+    for (const auto &owned_lock_info : own_list) {
+      const transaction_id owned_transaction = owned_lock_info.first;
+      const DirectedGraph::node_id owned_node = getNodeId(owned_transaction);
+
+      for (const auto &pending_lock_info : pending_list) {
+        const transaction_id pending_transaction = pending_lock_info.first;
+        const DirectedGraph::node_id pending_node = getNodeId(pending_transaction);
+
+        wait_for_graph_->addEdgeUnchecked(pending_node, owned_node);
+      }
+    }
+  }
+
+  lock_table_->unlatchShared();
+  // Critical region on LockTable ends here.
+
+  const CycleDetector cycle_detector(wait_for_graph_.get());
+  const std::vector<DirectedGraph::node_id> victim_nodes =
+      cycle_detector.chooseVictimsToBreakCycle();
+  for (const DirectedGraph::node_id node_id : victim_nodes) {
+    const transaction_id victim_tid = wait_for_graph_->getDataFromNode(node_id);
+    result_victims.push_back(victim_tid);
+  }
+
+  // Destroy the wait graph. It will be reconstructed kSleepDurationSeconds
+  // seconds later.
+  wait_for_graph_.reset();
+
+  return result_victims;
+}
+
+}  // namespace transaction
+}  // namespace quickstep

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/DeadLockDetector.hpp
----------------------------------------------------------------------
diff --git a/transaction/DeadLockDetector.hpp b/transaction/DeadLockDetector.hpp
new file mode 100644
index 0000000..6897afb
--- /dev/null
+++ b/transaction/DeadLockDetector.hpp
@@ -0,0 +1,156 @@
+/**
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
+ *
+ *   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.
+ **/
+
+#ifndef QUICKSTEP_TRANSACTION_DEAD_LOCK_DETECTOR_HPP_
+#define QUICKSTEP_TRANSACTION_DEAD_LOCK_DETECTOR_HPP_
+
+#include <atomic>
+#include <cstdint>
+#include <memory>
+#include <unordered_map>
+#include <vector>
+
+#include "threading/Thread.hpp"
+#include "transaction/DirectedGraph.hpp"
+#include "transaction/Transaction.hpp"
+
+namespace quickstep {
+namespace transaction {
+
+class LockTable;
+
+/** \addtogroup Transaction
+ *  @{
+ */
+
+/**
+ * @brief Notification mechanism between LockManager and DeadLockDetector.
+ **/
+enum class DeadLockDetectorStatus {
+  kNotReady = 0,
+  kDone,
+  kQuit,
+};
+
+/**
+ * @brief Class for deadlock detection on wait-for graph.
+ **/
+class DeadLockDetector : public Thread {
+ public:
+  typedef std::unordered_map<transaction_id, DirectedGraph::node_id>
+      transaction_id_node_map;
+
+  /**
+   * @brief Constructor for DeadLockDetector.
+   *
+   * @param lock_table Pointer to lock table, which this class gets the
+   *        necessary information.
+   * @param status Pointer to status object which will act as a message
+   *        passing algorithm between LockManager.
+   * @param victims Message passing buffer betwen DeadLockDetector and
+   *        LockManager.
+   **/
+  DeadLockDetector(LockTable *lock_table,
+                   std::atomic<DeadLockDetectorStatus> *status,
+                   std::vector<DirectedGraph::node_id> *victims);
+
+  void run() override;
+
+  /**
+   * @brief Adds pending information based on a resource conflict.
+   *
+   * @param pending Id of the transaction that waits for the resource lock.
+   * @param owner Id of the transaction that owns the resource lock.
+   */
+  void addPendingInfo(const transaction_id pending,
+                      const transaction_id owner);
+
+  /**
+   * @brief Deletes pending information on a resource.
+   *
+   * @param pending Id of the transaction that waits for the resource lock.
+   * @param owner Id of the transaction that owns the resource lock.
+   *
+   * @warning This method is not implemented yet.
+   */
+  void deletePendingInfo(const transaction_id pending,
+                         const transaction_id owner);
+
+  /**
+   * @brief Check whether first transaction waits for the latter.
+   *
+   * @param pending Id of the transaction which will be checked whether
+   *        it waits for the other.
+   * @param owner Id of the transaction which will be checked whether
+   *        it is waited by the first.
+   *
+   * @warning This method is not implemented yet.
+   */
+  bool isDependent(const transaction_id pending,
+                   const transaction_id owner) const;
+
+  /**
+   * @brief Gives the ids of transactions that wait for the owner transaction.
+   *
+   * @param owner Id of the transaction whose the penders will be returned.
+   * @return Vector of transaction ids that wait for owner.
+   */
+  std::vector<transaction_id> getAllDependents(const transaction_id owner) const;
+
+  /**
+   * @brief Gives the ids of transaction that the pending transaction waits for.
+   * @warning This method is not implemented yet.
+
+   * @param pending Id of the transaction that is pending.
+   * @return Vector of transaction ids which the pending transaction waits for.
+   */
+  std::vector<transaction_id> getAllDependees(transaction_id pending);
+
+  /**
+   * @brief Gives the list of victims whose the terminations will end the cycle.
+   *
+   * @return Vector of victim transaction ids.
+   */
+  std::vector<transaction_id> getAllVictims();
+
+ private:
+  static constexpr std::int64_t kSleepDurationInSeconds = 5;
+
+  DirectedGraph::node_id getNodeId(const transaction_id tid);
+
+  DirectedGraph::node_id addNode(const transaction_id tid);
+
+  // Owned pointer to wait-for graph.
+  std::unique_ptr<DirectedGraph> wait_for_graph_;
+
+  // Mapping from TransactioId to NodeId in graph.
+  std::unique_ptr<transaction_id_node_map> tid_node_mapping_;
+
+  // Pointer to lock table. Dependence edges will be created
+  // by the information got from lock table.
+  LockTable *lock_table_;
+
+  std::atomic<DeadLockDetectorStatus> *status_;
+  std::vector<DirectedGraph::node_id> *victims_;
+};
+
+/** @} */
+
+}  // namespace transaction
+}  // namespace quickstep
+
+#endif  // QUICKSTEP_TRANSACTION_DEAD_LOCK_DETECTOR_HPP_

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/DirectedGraph.hpp
----------------------------------------------------------------------
diff --git a/transaction/DirectedGraph.hpp b/transaction/DirectedGraph.hpp
index 89ce9c6..16b551a 100644
--- a/transaction/DirectedGraph.hpp
+++ b/transaction/DirectedGraph.hpp
@@ -21,8 +21,8 @@
 #include <algorithm>
 #include <cstddef>
 #include <cstdint>
+#include <iterator>
 #include <memory>
-#include <stack>
 #include <unordered_set>
 #include <vector>
 
@@ -39,7 +39,7 @@ namespace transaction {
  */
 
 /**
- * @brief Class for representing a directed graph. Vertices are transaction 
+ * @brief Class for representing a directed graph. Vertices are transaction
  *        ids, edges are wait-for relations.
  **/
 class DirectedGraph {
@@ -54,34 +54,31 @@ class DirectedGraph {
   /**
    * @brief Adds a new node to the graph with the given transaction id.
    *        It does not check whether the transaction id is valid or not.
-   * @warning Pointer ownership will pass to the graph, therefore it
-   *          should not be deleted.
    *
-   * @param data Pointer to the transaction id that will be contained
+   * @param transaction_id_payload Transaction id that will be contained
    *        in the node.
    * @return Id of the newly created node.
    **/
-  inline node_id addNodeUnchecked(transaction_id *data) {
-    nodes_.emplace_back(data);
+  inline
+  node_id addNodeUnchecked(const transaction_id transaction_id_payload) {
+    nodes_.emplace_back(transaction_id_payload);
     return nodes_.size() - 1;
   }
 
   /**
    * @brief Adds a new node to the graph with the given transaction id.
    *        It checks whether the transaction id is valid or not.
-   * @warning Pointer ownership will pass to the graph, therefore it
-   *          should not be deleted.
    *
-   * @param data Pointer to the transaction id that will be contained
+   * @param transaction_id_payload Transaction id that will be contained
    *        in the node.
    * @return Id of the newly created node.
    **/
-  inline node_id addNodeCheckExists(transaction_id *data) {
-    for (std::vector<DirectedGraphNode>::const_iterator
-           it = nodes_.cbegin(); it != nodes_.cend(); ++it) {
-      CHECK(*data != it->getData());
+  node_id addNodeCheckExists(const transaction_id transaction_id_payload) {
+    for (const auto &node : nodes_) {
+      CHECK(transaction_id_payload != node.getData());
     }
-    nodes_.emplace_back(data);
+
+    nodes_.emplace_back(transaction_id_payload);
     return nodes_.size() - 1;
   }
 
@@ -91,10 +88,10 @@ class DirectedGraph {
    * @warning Does not check arguments are legit. It may cause
    *          out of range errors.
    *
-   * @param fromNode The node that edge is orginated.
+   * @param fromNode The node that edge is originated.
    * @param toNode The node that edge is ended.
    **/
-  inline void addEdgeUnchecked(node_id from_node, node_id to_node) {
+  void addEdgeUnchecked(node_id from_node, node_id to_node) {
     nodes_[from_node].addOutgoingEdge(to_node);
   }
 
@@ -105,7 +102,7 @@ class DirectedGraph {
    * @param fromNode The node that edge is orginated.
    * @param toNode The node that edge is ended.
    **/
-  inline void addEdgeCheckExists(node_id from_node, node_id to_node) {
+  void addEdgeCheckExists(node_id from_node, node_id to_node) {
     CHECK(from_node < getNumNodes() && to_node < getNumNodes());
     nodes_[from_node].addOutgoingEdge(to_node);
   }
@@ -119,7 +116,7 @@ class DirectedGraph {
    * @param toNode Id of the node that edge is ended.
    * @return True if there is an edge, false otherwise.
    **/
-  inline bool hasEdge(node_id from_node, node_id to_node) const {
+  bool hasEdge(node_id from_node, node_id to_node) const {
     DCHECK(from_node < getNumNodes() && to_node < getNumNodes());
     return nodes_[from_node].hasOutgoingEdge(to_node);
   }
@@ -130,7 +127,7 @@ class DirectedGraph {
    * @param node Id of the node that the data is got from.
    * @return Id of the transaction that this node contains.
    **/
-  inline transaction_id getDataFromNode(node_id node) const {
+  transaction_id getDataFromNode(node_id node) const {
     DCHECK(node < getNumNodes());
     return nodes_[node].getData();
   }
@@ -140,7 +137,7 @@ class DirectedGraph {
    *
    * @return The number of nodes the graph has.
    **/
-  inline std::size_t getNumNodes() const {
+  std::size_t getNumNodes() const {
     return nodes_.size();
   }
 
@@ -158,18 +155,18 @@ class DirectedGraph {
   // Class for representing a graph node.
   class DirectedGraphNode {
    public:
-    explicit DirectedGraphNode(transaction_id *data)
-      : data_(data) {}
+    explicit DirectedGraphNode(const transaction_id payload)
+      : transaction_id_payload_(payload) {}
 
-    inline void addOutgoingEdge(node_id to_node) {
+    void addOutgoingEdge(node_id to_node) {
       outgoing_edges_.insert(to_node);
     }
 
-    inline bool hasOutgoingEdge(node_id to_node) const {
+    bool hasOutgoingEdge(node_id to_node) const {
       return outgoing_edges_.count(to_node) == 1;
     }
 
-    inline std::vector<node_id> getOutgoingEdges() const {
+    std::vector<node_id> getOutgoingEdges() const {
       // TODO(hakan): Benchmark this version and the alternative which the
       //              function returns const reference and the uniqueness
       //              is imposed in the outgoing_edges_ as a vector.
@@ -179,13 +176,12 @@ class DirectedGraph {
       return result;
     }
 
-    inline transaction_id getData() const {
-      return *(data_.get());
+    transaction_id getData() const {
+      return transaction_id_payload_;
     }
 
    private:
-    // Owner pointer to transaction id.
-    std::unique_ptr<transaction_id> data_;
+    const transaction_id transaction_id_payload_;
 
     // Endpoint nodes of outgoing edges originated from this node.
     std::unordered_set<node_id> outgoing_edges_;

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/LockManager.cpp
----------------------------------------------------------------------
diff --git a/transaction/LockManager.cpp b/transaction/LockManager.cpp
new file mode 100644
index 0000000..da6181a
--- /dev/null
+++ b/transaction/LockManager.cpp
@@ -0,0 +1,237 @@
+/**
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
+ *
+ *   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 "transaction/LockManager.hpp"
+
+#include <cstdint>
+#include <stack>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "transaction/AccessMode.hpp"
+#include "transaction/DeadLockDetector.hpp"
+#include "transaction/LockRequest.hpp"
+#include "transaction/LockTable.hpp"
+#include "transaction/ResourceId.hpp"
+#include "transaction/Transaction.hpp"
+#include "transaction/TransactionTable.hpp"
+#include "utility/ThreadSafeQueue.hpp"
+
+#include "gflags/gflags.h"
+#include "glog/logging.h"
+
+namespace quickstep {
+namespace transaction {
+
+DEFINE_uint64(max_try_incoming, 10000,
+              "The maximum number of tries that lock manager checks incoming "
+              "request buffer until the buffer is empty.");
+
+DEFINE_uint64(max_try_inner, 6000,
+              "The maximum number of tries that lock manager checks inner "
+              "request buffer until the buffer is empty.");
+
+LockManager::LockManager(ThreadSafeQueue<LockRequest> *incoming_requests,
+                         ThreadSafeQueue<LockRequest> *permitted_requests)
+    : lock_table_(std::make_unique<LockTable>()),
+      transaction_table_(std::make_unique<TransactionTable>()),
+      detector_status_(DeadLockDetectorStatus::kNotReady),
+      deadlock_detector_(std::make_unique<DeadLockDetector>(lock_table_.get(),
+                                                            &detector_status_,
+                                                            &victim_result_)),
+      incoming_requests_(*incoming_requests),
+      permitted_requests_(*permitted_requests),
+      inner_pending_requests_() {
+}
+
+LockManager::~LockManager() {
+  deadlock_detector_->join();
+}
+
+void LockManager::run() {
+  deadlock_detector_->start();
+
+  const std::uint64_t kMaxTryIncoming =
+      static_cast<std::uint64_t>(FLAGS_max_try_incoming);
+  const std::uint64_t kMaxTryInner =
+      static_cast<std::uint64_t>(FLAGS_max_try_incoming);
+
+  while (true) {
+    for (std::uint64_t tries = 0; tries < kMaxTryIncoming; ++tries) {
+      if (!incoming_requests_.empty()) {
+        const LockRequest request = incoming_requests_.popOne();
+        if (request.getRequestType() == RequestType::kReleaseLocks) {
+          CHECK(releaseAllLocks(request.getTransactionId()))
+              << "Unexpected condition occured.";
+
+        } else if (acquireLock(request.getTransactionId(),
+                               request.getResourceId(),
+                               request.getAccessMode())) {
+          LOG(INFO) << "Transaction "
+                    << std::to_string(request.getTransactionId())
+                    << " is waiting " + request.getResourceId().toString();
+
+            inner_pending_requests_.push(request);
+        } else {
+            LOG(INFO) << "Transaction "
+                      << std::to_string(request.getTransactionId())
+                      << " acquired " + request.getResourceId().toString();
+
+            permitted_requests_.push(request);
+        }
+      }
+    }
+
+    for (std::uint64_t tries = 0; tries < kMaxTryInner; ++tries) {
+      if (!inner_pending_requests_.empty()) {
+        const LockRequest request = inner_pending_requests_.front();
+
+        if (acquireLock(request.getTransactionId(), request.getResourceId(),
+                        request.getAccessMode())) {
+          inner_pending_requests_.pop();
+          permitted_requests_.push(request);
+        }
+      }
+    }
+
+    // Resolve deadlocks.
+    killVictims();
+  }
+}
+
+bool LockManager::acquireLock(const transaction_id tid,
+                              const ResourceId &rid,
+                              const AccessMode &access_mode) {
+  std::stack<std::pair<ResourceId, AccessMode>> stack;
+  ResourceId current_rid = rid;
+  AccessMode current_access_mode = access_mode;
+  stack.push(std::make_pair(current_rid, current_access_mode));
+
+  while (current_rid.hasParent()) {
+    current_rid = current_rid.getParentResourceId();
+    current_access_mode = (current_access_mode.isShareLock() ||
+                           current_access_mode.isIntentionShareLock())
+                              ? AccessMode(AccessMode::IsLockMode())
+                              : AccessMode(AccessMode::IxLockMode());
+
+    stack.push(std::make_pair(current_rid, current_access_mode));
+  }
+
+  lock_table_->latchExclusive();
+
+  while (!stack.empty()) {
+    const std::pair<ResourceId, AccessMode> pair_to_pick = stack.top();
+    const ResourceId rid_to_pick = pair_to_pick.first;
+    const AccessMode access_mode_to_pick = pair_to_pick.second;
+
+    if (!acquireLockInternal(tid, rid_to_pick, access_mode_to_pick)) {
+      lock_table_->unlatchExclusive();
+      return false;
+    }
+    stack.pop();
+  }
+  lock_table_->unlatchExclusive();
+  return true;
+}
+
+bool LockManager::releaseAllLocks(const transaction_id tid,
+                                  const bool latch_table) {
+  const std::vector<ResourceId> resource_ids
+      = transaction_table_->getResourceIdList(tid);
+  const TransactionTableResult transaction_deleted
+      = transaction_table_->deleteTransaction(tid);
+
+  CHECK(transaction_deleted != TransactionTableResult::kTransactionDeleteError)
+      << "In LockManager.releaseAllLocks: Transaction could not be deleted!";
+
+  if (latch_table) {
+    lock_table_->latchExclusive();
+  }
+  for (const auto &resource_id : resource_ids) {
+    const LockTableResult lock_deleted = lock_table_->deleteLock(tid, resource_id);
+
+    LOG(INFO) << "Transaction "
+              << std::to_string(tid)
+              << " released lock:"
+              << resource_id.toString();
+    CHECK(lock_deleted != LockTableResult::kDeleteError)
+        << "In LockManager.releaseAllLock lock could not be deleted from "
+           "LockTable";
+  }
+  if (latch_table) {
+    lock_table_->unlatchExclusive();
+  }
+  return true;
+}
+
+bool LockManager::acquireLockInternal(const transaction_id tid,
+                                      const ResourceId &rid,
+                                      const AccessMode &access_mode) {
+  const LockTableResult lock_result = lock_table_->putLock(tid, rid, access_mode);
+  CHECK(lock_result != LockTableResult::kPutError)
+      << "Unexpected result in LockManager.acquireLockInternal";
+
+  switch (lock_result) {
+  case LockTableResult::kAlreadyInOwned: {
+    return true;
+  }
+  case LockTableResult::kPlacedInOwned: {
+    const TransactionTableResult transaction_result
+        = transaction_table_->putOwnEntry(tid, rid, access_mode);
+    CHECK(transaction_result == TransactionTableResult::kPlacedInOwned)
+        << "Unexpected result in LockManager.acquireLockInternal: "
+           "Mismatch of table results: LockTable entry is owned, "
+           "whereas TransactionTable entry is not owned.";
+    return true;
+  }
+  case LockTableResult::kAlreadyInPending: {
+    return false;
+  }
+  case LockTableResult::kPlacedInPending: {
+    const TransactionTableResult transaction_result =
+      transaction_table_->putPendingEntry(tid, rid, access_mode);
+    CHECK(transaction_result == TransactionTableResult::kPlacedInPending)
+        << "Unexpected result in LockManager.acquireLockInternal: "
+           "Mismatch of table results: LockTable entry is pending, "
+           "whereas TransactionTable entry is not pending";
+    return false;
+  }
+  default: {
+    return false;
+  }
+  }
+}
+
+void LockManager::killVictims() {
+  if (detector_status_.load() == DeadLockDetectorStatus::kDone) {
+    lock_table_->latchExclusive();
+    for (const auto victim_transaction_id : victim_result_) {
+      releaseAllLocks(victim_transaction_id, false);
+      // TODO(Hakan): Find a way to kill transaction, so that requests with this
+      //              tid should be ignored.
+      LOG(INFO) << "Killed transaction "
+                << std::to_string(victim_transaction_id);
+    }
+    lock_table_->unlatchExclusive();
+  }
+  victim_result_.clear();
+  detector_status_.store(DeadLockDetectorStatus::kNotReady);
+}
+
+}  // namespace transaction
+}  // namespace quickstep

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/LockManager.hpp
----------------------------------------------------------------------
diff --git a/transaction/LockManager.hpp b/transaction/LockManager.hpp
new file mode 100644
index 0000000..40ee6c8
--- /dev/null
+++ b/transaction/LockManager.hpp
@@ -0,0 +1,128 @@
+/**
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
+ *
+ *   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.
+ **/
+
+#ifndef QUICKSTEP_TRANSACTION_LOCK_MANAGER_HPP_
+#define QUICKSTEP_TRANSACTION_LOCK_MANAGER_HPP_
+
+#include <atomic>
+#include <memory>
+#include <queue>
+#include <vector>
+
+#include "threading/Thread.hpp"
+#include "transaction/DeadLockDetector.hpp"
+#include "transaction/LockRequest.hpp"
+#include "transaction/Transaction.hpp"
+
+namespace quickstep {
+
+template <typename T> class ThreadSafeQueue;
+
+namespace transaction {
+
+class AccessMode;
+class LockTable;
+class ResourceId;
+class TransactionTable;
+
+/** \addtogroup Transaction
+ *  @{
+ **/
+
+/**
+ * @brief Class for centralized location of acquisition and releasing
+ *        of resource locks.
+ **/
+class LockManager : public Thread {
+ public:
+  /**
+   * @brief Constructor
+   *
+   * @param incoming_requests Queue for the lock requests that are waiting
+   *        for the permission.
+   * @param permitted_requests Queue for the lock requests that are granted
+   *        permission.
+   **/
+  LockManager(ThreadSafeQueue<LockRequest> *incoming_requests,
+              ThreadSafeQueue<LockRequest> *permitted_requests);
+
+  /**
+   * @brief Destructor for LockManager. It handles the thread
+   *        joins that it owns.
+   **/
+  ~LockManager();
+
+  /**
+   * @brief Method for defining the LockManager's thread main logic.
+   *
+   * @warning Users must not use this function directly. Instead use
+   *          start() method inherited from the Thread class.
+   **/
+  void run() override;
+
+  /**
+   * @brief Acquires the lock on resource with specified access mode.
+   *
+   * @param tid Id of the transaction which the resource lock is acquired for.
+   * @param rid Id of the resource on which the resource lock is acquired.
+   * @param access_mode Permissible access mode on resource.
+   *
+   * @return True if it can acquire the lock from root to leaf lock hierarchy,
+   *         false otherwise.
+   **/
+  bool acquireLock(const transaction_id tid,
+                   const ResourceId &rid,
+                   const AccessMode &access_mode);
+
+  /**
+   * @brief Releases all locks hold by the transaction.
+   *
+   * @param tid Id of the transaction whose locks will be released.
+   * @param latch_table If it is true, the method latch the whole
+   *        lock table, which is default.
+   * @return True if tid releases all of its locks.
+   **/
+  bool releaseAllLocks(const transaction_id tid,
+                       const bool latch_table = true);
+
+  /**
+   * @brief Release the locks acquired by the transactions contained
+   *        in victim buffer to break the deadlock.
+   **/
+  void killVictims();
+
+ private:
+  bool acquireLockInternal(const transaction_id tid,
+                           const ResourceId &rid,
+                           const AccessMode &access_mode);
+
+  std::unique_ptr<LockTable> lock_table_;
+  std::unique_ptr<TransactionTable> transaction_table_;
+  std::atomic<DeadLockDetectorStatus> detector_status_;
+  std::vector<transaction_id> victim_result_;
+  std::unique_ptr<DeadLockDetector> deadlock_detector_;
+  ThreadSafeQueue<LockRequest> &incoming_requests_;
+  ThreadSafeQueue<LockRequest> &permitted_requests_;
+  std::queue<LockRequest> inner_pending_requests_;
+};
+
+/** @} */
+
+}  // namespace transaction
+}  // namespace quickstep
+
+#endif  // QUICKSTEP_TRANSACTION_LOCK_MANAGER_HPP_

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/LockTable.cpp
----------------------------------------------------------------------
diff --git a/transaction/LockTable.cpp b/transaction/LockTable.cpp
index 77986f6..7b568fc 100644
--- a/transaction/LockTable.cpp
+++ b/transaction/LockTable.cpp
@@ -18,15 +18,11 @@
 #include "transaction/LockTable.hpp"
 
 #include <list>
-#include <unordered_map>
 #include <utility>
 
-#include "threading/SharedMutex.hpp"
 #include "transaction/AccessMode.hpp"
 #include "transaction/Lock.hpp"
-#include "transaction/ResourceId.hpp"
 #include "transaction/Transaction.hpp"
-#include "utility/Macros.hpp"
 
 namespace quickstep {
 namespace transaction {
@@ -34,7 +30,7 @@ namespace transaction {
 LockTableResult
 LockTable::putLock(const transaction_id tid,
                    const ResourceId &rid,
-                   const AccessMode access_mode) {
+                   const AccessMode &access_mode) {
   // TODO(hakan): Lock upgrade is not supported.
   lock_list_pair &lock_list_pair = internal_map_[rid];
 
@@ -47,7 +43,7 @@ LockTable::putLock(const transaction_id tid,
   for (lock_own_list::const_iterator it = lock_own_list.cbegin();
        it != lock_own_list.cend(); ++it) {
     if (it->first == tid && it->second.getAccessMode() == access_mode) {
-      return LockTableResult::kALREADY_IN_OWNED;
+      return LockTableResult::kAlreadyInOwned;
     }
   }
 
@@ -56,7 +52,7 @@ LockTable::putLock(const transaction_id tid,
   for (lock_pending_list::const_iterator it = lock_pending_list.cbegin();
        it != lock_pending_list.cend(); ++it) {
     if (it->first == tid && it->second.getAccessMode() == access_mode) {
-      return LockTableResult::kALREADY_IN_PENDING;
+      return LockTableResult::kAlreadyInPending;
     }
   }
 
@@ -68,18 +64,18 @@ LockTable::putLock(const transaction_id tid,
       if (!access_mode.isCompatible(it->second.getAccessMode())) {
         lock_pending_list.push_back(std::make_pair(tid,
                                                    Lock(rid, access_mode)));
-        return LockTableResult::kPLACED_IN_PENDING;
+        return LockTableResult::kPlacedInPending;
       }
     }
 
     lock_own_list.push_back(std::make_pair(tid, Lock(rid, access_mode)));
-    return LockTableResult::kPLACED_IN_OWNED;
+    return LockTableResult::kPlacedInOwned;
   } else {
     // If the pending list is not empty, even if the lock request is compatible
     // with other owned lock entries, we put the new request into the pending
     // list to eliminate starvation.
     lock_pending_list.push_back(std::make_pair(tid, Lock(rid, access_mode)));
-    return LockTableResult::kPLACED_IN_PENDING;
+    return LockTableResult::kPlacedInPending;
   }
 }
 
@@ -105,7 +101,7 @@ LockTable::deleteLock(const transaction_id tid,
       // compatible with the remaining owned entries.
       movePendingToOwned(rid);
 
-      return LockTableResult::kDEL_FROM_OWNED;
+      return LockTableResult::kDeleteFromOwned;
     }
   }
 
@@ -116,13 +112,13 @@ LockTable::deleteLock(const transaction_id tid,
     if (it->first == tid) {
       // If it exists, erase it from pending list.
       lock_pending_list.erase(it);
-      return LockTableResult::kDEL_FROM_PENDING;
+      return LockTableResult::kDeleteFromPending;
     }
   }
 
   // Execution reaches here, if we cannot find the corresponding lock entry
   // in the both list.
-  return LockTableResult::kDEL_ERROR;
+  return LockTableResult::kDeleteError;
 }
 
 void LockTable::movePendingToOwned(const ResourceId &rid) {

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/LockTable.hpp
----------------------------------------------------------------------
diff --git a/transaction/LockTable.hpp b/transaction/LockTable.hpp
index 5a0612e..529db12 100644
--- a/transaction/LockTable.hpp
+++ b/transaction/LockTable.hpp
@@ -23,7 +23,6 @@
 #include <utility>
 
 #include "threading/SharedMutex.hpp"
-#include "transaction/AccessMode.hpp"
 #include "transaction/Lock.hpp"
 #include "transaction/ResourceId.hpp"
 #include "transaction/Transaction.hpp"
@@ -32,6 +31,8 @@
 namespace quickstep {
 namespace transaction {
 
+class AccessMode;
+
 /** \addtogroup Transaction
  * @{
  */
@@ -40,14 +41,14 @@ namespace transaction {
  * @brief Represents different results for LockTable's methods.
  **/
 enum class LockTableResult {
-  kPLACED_IN_OWNED = 0,
-  kPLACED_IN_PENDING,
-  kALREADY_IN_OWNED,
-  kALREADY_IN_PENDING,
-  kDEL_FROM_OWNED,
-  kDEL_FROM_PENDING,
-  kDEL_ERROR,
-  kPUT_ERROR,
+  kPlacedInOwned = 0,
+  kPlacedInPending,
+  kAlreadyInOwned,
+  kAlreadyInPending,
+  kDeleteFromOwned,
+  kDeleteFromPending,
+  kDeleteError,
+  kPutError,
 };
 
 /**
@@ -79,32 +80,31 @@ class LockTable {
    * @param rid Id of the resource to be locked.
    * @param access_mode Access mode of the lock.
    *
-   * @return LockTableResult::kPLACED_IN_OWNED if lock is granted,
-   *         LockTableResult::kPLACED_IN_PENDING if lock is not granted,
-   *         LockTableResult::kALREADY_IN_OWNED if lock has been
+   * @return LockTableResult::kPlacedInOwned if lock is granted,
+   *         LockTableResult::kPlacedInPending if lock is not granted,
+   *         LockTableResult::kAlreadyInOwned if lock has been
    *         already granted,
-   *         LockTableResult::kALREADY_IN_PENDING if lock has been
+   *         LockTableResult::kAlreadyInPending if lock has been
    *         already pending.
    **/
   LockTableResult putLock(const transaction_id tid,
                           const ResourceId &rid,
-                          const AccessMode access_mode);
+                          const AccessMode &access_mode);
   /**
    * @brief Deletes the lock entry.
    *
    * @param tid Id of the transaction that owns or awaits.
    * @param rid Id of resource that the lock covers.
    *
-   * @return LockTableResult::kDEL_FROM_OWNED if the lock is deleted from
+   * @return LockTableResult::kDelFromOwned if the lock is deleted from
    *         owned list,
-   *         LockTableResult::kDEL_FROM_PENDING if the lock is deleted from
+   *         LockTableResult::kDelFromPending if the lock is deleted from
    *         pending list,
-   *         LockTableResult::kDEL_ERROR if the lock cannot be found
+   *         LockTableResult::kDelError if the lock cannot be found
    **/
   LockTableResult deleteLock(const transaction_id tid,
                              const ResourceId &rid);
 
-
   /**
    * @brief Iterator for begin position.
    *

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/ResourceId.hpp
----------------------------------------------------------------------
diff --git a/transaction/ResourceId.hpp b/transaction/ResourceId.hpp
index b9d1cdf..3a770dd 100644
--- a/transaction/ResourceId.hpp
+++ b/transaction/ResourceId.hpp
@@ -19,7 +19,6 @@
 #define QUICKSTEP_TRANSACTION_RESOURCE_ID_HPP_
 
 #include <cstddef>
-#include <limits>
 #include <string>
 
 #include "catalog/CatalogTypedefs.hpp"
@@ -202,10 +201,10 @@ class ResourceId {
     return tuple_id_ == kTupleIdPlaceholder;
   }
 
-  const database_id db_id_;
-  const relation_id rel_id_;
-  const block_id block_id_;
-  const tuple_id tuple_id_;
+  database_id db_id_;
+  relation_id rel_id_;
+  block_id block_id_;
+  tuple_id tuple_id_;
 };
 
 /** @} */

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/StronglyConnectedComponents.cpp
----------------------------------------------------------------------
diff --git a/transaction/StronglyConnectedComponents.cpp b/transaction/StronglyConnectedComponents.cpp
index 89daf46..f50ed85 100644
--- a/transaction/StronglyConnectedComponents.cpp
+++ b/transaction/StronglyConnectedComponents.cpp
@@ -17,7 +17,6 @@
 
 #include "transaction/StronglyConnectedComponents.hpp"
 
-#include <cstddef>
 #include <cstdint>
 #include <stack>
 #include <unordered_map>

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/Transaction.cpp
----------------------------------------------------------------------
diff --git a/transaction/Transaction.cpp b/transaction/Transaction.cpp
deleted file mode 100644
index 3478d01..0000000
--- a/transaction/Transaction.cpp
+++ /dev/null
@@ -1,48 +0,0 @@
-/**
- *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
- *     University of Wisconsin—Madison.
- *
- *   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 "transaction/Transaction.hpp"
-
-#include <functional>
-
-namespace quickstep {
-
-namespace transaction {
-
-TransactionId Transaction::getTransactionId() const {
-  return tid_;
-}
-
-void Transaction::setStatus(TransactionStatus status) {
-  status_ = status;
-}
-
-TransactionStatus Transaction::getStatus() const {
-  return status_;
-}
-
-bool Transaction::operator==(const Transaction &other) const {
-  return tid_ == other.tid_;
-}
-
-std::size_t Transaction::TransactionHasher::operator()(const Transaction &transaction) const {
-  return std::hash<TransactionId>()(transaction.tid_);
-}
-
-}  // namespace transaction
-
-}  // namespace quickstep

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/TransactionTable.cpp
----------------------------------------------------------------------
diff --git a/transaction/TransactionTable.cpp b/transaction/TransactionTable.cpp
index 993703a..3e37439 100644
--- a/transaction/TransactionTable.cpp
+++ b/transaction/TransactionTable.cpp
@@ -33,7 +33,7 @@ namespace transaction {
 TransactionTableResult
 TransactionTable::putOwnEntry(const transaction_id tid,
                               const ResourceId &rid,
-                              const AccessMode access_mode) {
+                              const AccessMode &access_mode) {
   transaction_list_pair &transaction_list_pair = internal_map_[tid];
   transaction_own_list &transaction_own_list = transaction_list_pair.first;
 
@@ -45,7 +45,7 @@ TransactionTable::putOwnEntry(const transaction_id tid,
 TransactionTableResult
 TransactionTable::putPendingEntry(const transaction_id tid,
                                   const ResourceId &rid,
-                                  const AccessMode access_mode) {
+                                  const AccessMode &access_mode) {
   transaction_list_pair &transaction_list_pair = internal_map_[tid];
   transaction_pending_list &transaction_pending_list
       = transaction_list_pair.second;
@@ -59,7 +59,7 @@ TransactionTable::putPendingEntry(const transaction_id tid,
 TransactionTableResult
 TransactionTable::deleteOwnEntry(const transaction_id tid,
                                  const ResourceId &rid,
-                                 const AccessMode access_mode) {
+                                 const AccessMode &access_mode) {
   transaction_list_pair &transaction_list_pair = internal_map_[tid];
   transaction_own_list &transaction_own_list = transaction_list_pair.first;
 
@@ -79,7 +79,7 @@ TransactionTable::deleteOwnEntry(const transaction_id tid,
 TransactionTableResult
 TransactionTable::deletePendingEntry(const transaction_id tid,
                                      const ResourceId &rid,
-                                     const AccessMode access_mode) {
+                                     const AccessMode &access_mode) {
   transaction_list_pair &transaction_list_pair = internal_map_[tid];
   transaction_pending_list &transaction_pending_list
       = transaction_list_pair.second;

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/TransactionTable.hpp
----------------------------------------------------------------------
diff --git a/transaction/TransactionTable.hpp b/transaction/TransactionTable.hpp
index a5e1da4..29df536 100644
--- a/transaction/TransactionTable.hpp
+++ b/transaction/TransactionTable.hpp
@@ -23,7 +23,6 @@
 #include <utility>
 #include <vector>
 
-#include "transaction/AccessMode.hpp"
 #include "transaction/Lock.hpp"
 #include "transaction/ResourceId.hpp"
 #include "transaction/Transaction.hpp"
@@ -32,6 +31,8 @@
 namespace quickstep {
 namespace transaction {
 
+class AccessMode;
+
 /** \addtogroup Transaction
  *  @{
  */
@@ -81,7 +82,7 @@ class TransactionTable {
    **/
   TransactionTableResult putOwnEntry(const transaction_id tid,
                                      const ResourceId &rid,
-                                     const AccessMode access_mode);
+                                     const AccessMode &access_mode);
 
   /**
    * @brief Puts a pending entry of the given resource id in the given
@@ -95,7 +96,7 @@ class TransactionTable {
    **/
   TransactionTableResult putPendingEntry(const transaction_id tid,
                                          const ResourceId &rid,
-                                         const AccessMode access_mode);
+                                         const AccessMode &access_mode);
 
   /**
    * @brief Deletes the owned entry corresponding to the resource id
@@ -110,7 +111,7 @@ class TransactionTable {
    **/
   TransactionTableResult deleteOwnEntry(const transaction_id tid,
                                         const ResourceId &rid,
-                                        const AccessMode access_mode);
+                                        const AccessMode &access_mode);
 
   /**
    * @brief Deletes the pending entry corresponding to the resource id
@@ -124,7 +125,7 @@ class TransactionTable {
    **/
   TransactionTableResult deletePendingEntry(const transaction_id tid,
                                             const ResourceId &rid,
-                                            const AccessMode access_mode);
+                                            const AccessMode &access_mode);
 
   /**
    * @brief Returns a vector of resource ids which the corresponding transaction

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/tests/AccessMode_unittest.cpp
----------------------------------------------------------------------
diff --git a/transaction/tests/AccessMode_unittest.cpp b/transaction/tests/AccessMode_unittest.cpp
index fa51525..3287fb0 100644
--- a/transaction/tests/AccessMode_unittest.cpp
+++ b/transaction/tests/AccessMode_unittest.cpp
@@ -25,12 +25,12 @@ namespace transaction {
 class AccessModeTest : public ::testing::Test {
  protected:
   AccessModeTest()
-      : nl_mode_(AccessModeType::kNoLock),
-        is_mode_(AccessModeType::kIsLock),
-        ix_mode_(AccessModeType::kIxLock),
-        s_mode_(AccessModeType::kSLock),
-        six_mode_(AccessModeType::kSixLock),
-        x_mode_(AccessModeType::kXLock) {
+      : nl_mode_(AccessMode::NoLockMode()),
+        is_mode_(AccessMode::IsLockMode()),
+        ix_mode_(AccessMode::IxLockMode()),
+        s_mode_(AccessMode::SLockMode()),
+        six_mode_(AccessMode::SixLockMode()),
+        x_mode_(AccessMode::XLockMode()) {
   }
 
   const AccessMode nl_mode_;

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/tests/CycleDetector_unittest.cpp
----------------------------------------------------------------------
diff --git a/transaction/tests/CycleDetector_unittest.cpp b/transaction/tests/CycleDetector_unittest.cpp
new file mode 100644
index 0000000..6edaa63
--- /dev/null
+++ b/transaction/tests/CycleDetector_unittest.cpp
@@ -0,0 +1,157 @@
+/**
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
+ *
+ *   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 "transaction/CycleDetector.hpp"
+
+#include <cstdint>
+#include <memory>
+#include <stack>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+#include "transaction/DirectedGraph.hpp"
+#include "transaction/Transaction.hpp"
+
+#include "gtest/gtest.h"
+
+namespace quickstep {
+namespace transaction {
+
+class CycleDetectorTest : public testing::Test {
+ protected:
+  const std::uint64_t kNumberOfTransactions = 12;
+
+  CycleDetectorTest()
+      : wait_for_graph_(std::make_unique<DirectedGraph>()) {
+  }
+
+  virtual void SetUp() {
+    std::vector<transaction_id> transactions(kNumberOfTransactions);
+    for (std::uint64_t i = 0; i < kNumberOfTransactions; ++i) {
+      transactions.push_back(transaction_id(i));
+    }
+
+    std::vector<DirectedGraph::node_id> node_ids;
+    for (std::uint64_t i = 0; i < kNumberOfTransactions; ++i) {
+      node_ids.push_back(wait_for_graph_->addNodeUnchecked(transactions[i]));
+    }
+  }
+
+  void initializeCycleDetector() {
+    for (const auto &edge : edges_) {
+      wait_for_graph_->addEdgeUnchecked(edge.first, edge.second);
+    }
+
+    cycle_detector_.reset(new CycleDetector(wait_for_graph_.get()));
+  }
+
+  void checkVictims(
+      const std::unordered_set<DirectedGraph::node_id> &expected_victims) {
+    const std::vector<DirectedGraph::node_id> victims =
+        cycle_detector_->chooseVictimsToBreakCycle();
+
+    std::unordered_set<DirectedGraph::node_id> remaining_nodes;
+
+    for (DirectedGraph::node_id node = 0; node < wait_for_graph_->getNumNodes();
+         ++node) {
+      if (std::find(victims.begin(), victims.end(), node) == victims.end()) {
+        // Node is not in victims, then insert it to remaining set.
+        remaining_nodes.insert(node);
+      }
+    }
+
+    for (const auto node : remaining_nodes) {
+      ASSERT_FALSE(isSelfReachableNode(node, remaining_nodes));
+    }
+  }
+
+  bool isSelfReachableNode(
+      const DirectedGraph::node_id start_node,
+      const std::unordered_set<DirectedGraph::node_id> &node_set) {
+    std::unordered_set<DirectedGraph::node_id> marked_nodes;
+    std::stack<DirectedGraph::node_id> to_be_visied_nodes;
+
+    const std::vector<DirectedGraph::node_id> neighbors_of_start_node =
+        wait_for_graph_->getAdjacentNodes(start_node);
+    for (const auto node : neighbors_of_start_node) {
+      marked_nodes.insert(node);
+      to_be_visied_nodes.push(node);
+    }
+
+    while (!to_be_visied_nodes.empty()) {
+      const DirectedGraph::node_id current_node = to_be_visied_nodes.top();
+      to_be_visied_nodes.pop();
+      if (current_node == start_node) {
+        return true;
+      }
+      if (node_set.count(current_node) == 1 &&
+          marked_nodes.count(current_node) == 0) {
+        // Means, we did not visited this node yet, and it is in the node set,
+        // so we should process it (mark it and push all of its neighbors
+        // into stack).
+        marked_nodes.insert(current_node);
+        const auto neighbors = wait_for_graph_->getAdjacentNodes(current_node);
+        for (const auto neighbor : neighbors) {
+          to_be_visied_nodes.push(neighbor);
+        }
+      }
+    }
+    return false;
+  }
+
+  std::vector<std::pair<DirectedGraph::node_id, DirectedGraph::node_id>> edges_;
+  std::unique_ptr<DirectedGraph> wait_for_graph_;
+  std::unique_ptr<CycleDetector> cycle_detector_;
+};
+
+TEST_F(CycleDetectorTest, Interleaving) {
+  edges_ = {{0, 1},
+            {1, 0}};
+
+  initializeCycleDetector();
+
+  std::unordered_set<DirectedGraph::node_id> expected_victims = {1};
+
+  checkVictims(expected_victims);
+}
+
+TEST_F(CycleDetectorTest, MultipleCycle) {
+  // This edge contains lots of cycles of degree 1, 2 and 3.
+  edges_ = {{0, 1},
+            {1, 2}, {1, 3}, {1, 4},
+            {2, 5},
+            {3, 4}, {3, 6},
+            {4, 1}, {4, 5}, {4, 6},
+            {5, 2}, {5, 7},
+            {6, 7}, {6, 9},
+            {7, 6},
+            {8, 6},
+            {9, 8}, {9, 10},
+            {10, 11},
+            {11, 9}};
+
+  initializeCycleDetector();
+
+  std::unordered_set<DirectedGraph::node_id> expected_victims
+      = {4, 5, 7, 8, 9, 10, 11};
+
+  checkVictims(expected_victims);
+}
+
+}  // namespace transaction
+}  // namespace quickstep

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/tests/DeadLockDetector_unittest.cpp
----------------------------------------------------------------------
diff --git a/transaction/tests/DeadLockDetector_unittest.cpp b/transaction/tests/DeadLockDetector_unittest.cpp
new file mode 100644
index 0000000..bc65ef5
--- /dev/null
+++ b/transaction/tests/DeadLockDetector_unittest.cpp
@@ -0,0 +1,96 @@
+/**
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
+ *
+ *   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 "transaction/DeadLockDetector.hpp"
+
+#include <atomic>
+#include <memory>
+#include <vector>
+
+#include "transaction/AccessMode.hpp"
+#include "transaction/DirectedGraph.hpp"
+#include "transaction/LockTable.hpp"
+#include "transaction/ResourceId.hpp"
+#include "transaction/Transaction.hpp"
+
+#include "gtest/gtest.h"
+
+namespace quickstep {
+namespace transaction {
+
+class DeadLockDetectorTest : public ::testing::Test {
+ protected:
+  DeadLockDetectorTest()
+      : lock_table_(std::make_unique<LockTable>()),
+        status_(DeadLockDetectorStatus::kDone) {
+  }
+
+  std::unique_ptr<LockTable> lock_table_;
+  std::atomic<DeadLockDetectorStatus> status_;
+  std::vector<DirectedGraph::node_id> victims_;
+};
+
+TEST_F(DeadLockDetectorTest, SimpleCycle) {
+  const transaction_id transaction_one(1), transaction_two(2);
+  const ResourceId resource_one(1, 2), resource_two(4, 5);
+
+  const AccessMode x_lock_mode(AccessMode::XLockMode());
+
+  // Produce a conflicting schedule.
+  // Transaction 1 will acquire X lock on resource 1.
+  lock_table_->putLock(transaction_one,
+                       resource_one,
+                       x_lock_mode);
+
+  // Transaction 2 will acquire X lock on resource 2.
+  lock_table_->putLock(transaction_two,
+                       resource_two,
+                       x_lock_mode);
+
+  // Transaction 1 will try to acquire X lock on resource 2,
+  // but it will fail since Transaction 2 has already acquired
+  // X lock on resource 2.
+  lock_table_->putLock(transaction_one,
+                       resource_two,
+                       x_lock_mode);
+
+  // Transaction 2 will try to acquire X lock on resource 1,
+  // but it will fail since Transaction 1 has already acquired
+  // X lock on resource 2.
+  lock_table_->putLock(transaction_two,
+                       resource_one,
+                       x_lock_mode);
+
+  // Run deadlock detector.
+  DeadLockDetector deadlock_detector(lock_table_.get(), &status_, &victims_);
+  status_.store(DeadLockDetectorStatus::kNotReady);
+
+  deadlock_detector.start();
+
+  // Signal deadlock detector.
+  while (status_.load() == DeadLockDetectorStatus::kNotReady) {
+  }
+
+  status_.store(DeadLockDetectorStatus::kQuit);
+  deadlock_detector.join();
+
+  // Victim size must be 1.
+  ASSERT_EQ(1u, victims_.size());
+}
+
+}  // namespace transaction
+}  // namespace quickstep

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/tests/DirectedGraph_unittest.cpp
----------------------------------------------------------------------
diff --git a/transaction/tests/DirectedGraph_unittest.cpp b/transaction/tests/DirectedGraph_unittest.cpp
index 43ad972..00fe276 100644
--- a/transaction/tests/DirectedGraph_unittest.cpp
+++ b/transaction/tests/DirectedGraph_unittest.cpp
@@ -26,101 +26,96 @@
 namespace quickstep {
 namespace transaction {
 
-TEST(DirectedGraphTest, AddNode) {
-  // Prepare the data, but do not include in the graph.
-  DirectedGraph wait_for_graph;
-  transaction_id *tid3 = new transaction_id(3);
-  transaction_id *tid4 = new transaction_id(4);
-  transaction_id *tid5 = new transaction_id(5);
-  transaction_id *tid6 = new transaction_id(6);
-
+class DirectedGraphTest : public ::testing::Test {
+ protected:
+  DirectedGraphTest()
+      : tid3_(3),
+        tid4_(4),
+        tid5_(5),
+        tid6_(6) {
+  }
+
+  DirectedGraph wait_for_graph_;
+  transaction_id tid3_;
+  transaction_id tid4_;
+  transaction_id tid5_;
+  transaction_id tid6_;
+};
+
+TEST_F(DirectedGraphTest, AddNode) {
   // The nodes are not added yet, total no of nodesshould be zero.
-  EXPECT_EQ(0u, wait_for_graph.getNumNodes());
+  EXPECT_EQ(0u, wait_for_graph_.getNumNodes());
 
-  wait_for_graph.addNodeUnchecked(tid3);
+  wait_for_graph_.addNodeUnchecked(tid3_);
 
   // One node is added.
-  EXPECT_EQ(1u, wait_for_graph.getNumNodes());
+  EXPECT_EQ(1u, wait_for_graph_.getNumNodes());
 
-  wait_for_graph.addNodeUnchecked(tid4);
+  wait_for_graph_.addNodeUnchecked(tid4_);
 
   // Another node is added.
-  EXPECT_EQ(2u, wait_for_graph.getNumNodes());
+  EXPECT_EQ(2u, wait_for_graph_.getNumNodes());
 
-  wait_for_graph.addNodeUnchecked(tid5);
-  wait_for_graph.addNodeUnchecked(tid6);
+  wait_for_graph_.addNodeUnchecked(tid5_);
+  wait_for_graph_.addNodeUnchecked(tid6_);
 
   // Total no of nodes should be 4 right now.
-  EXPECT_EQ(4u, wait_for_graph.getNumNodes());
+  EXPECT_EQ(4u, wait_for_graph_.getNumNodes());
 }
 
-TEST(DirectedGraphTest, AddEdge) {
-  // Prepare the graph.
-  DirectedGraph wait_for_graph;
-  transaction_id *tid3 = new transaction_id(3);
-  transaction_id *tid4 = new transaction_id(4);
-  transaction_id *tid5 = new transaction_id(5);
-  transaction_id *tid6 = new transaction_id(6);
-
-  DirectedGraph::node_id nid3 = wait_for_graph.addNodeUnchecked(tid3);
-  DirectedGraph::node_id nid6 = wait_for_graph.addNodeUnchecked(tid6);
-  DirectedGraph::node_id nid4 = wait_for_graph.addNodeUnchecked(tid4);
-  DirectedGraph::node_id nid5 = wait_for_graph.addNodeUnchecked(tid5);
+TEST_F(DirectedGraphTest, AddEdge) {
+  DirectedGraph::node_id nid3 = wait_for_graph_.addNodeUnchecked(tid3_);
+  DirectedGraph::node_id nid6 = wait_for_graph_.addNodeUnchecked(tid6_);
+  DirectedGraph::node_id nid4 = wait_for_graph_.addNodeUnchecked(tid4_);
+  DirectedGraph::node_id nid5 = wait_for_graph_.addNodeUnchecked(tid5_);
 
   // Add edges.
-  wait_for_graph.addEdgeUnchecked(nid3, nid5);
-  wait_for_graph.addEdgeUnchecked(nid6, nid4);
-  wait_for_graph.addEdgeUnchecked(nid3, nid6);
-  wait_for_graph.addEdgeUnchecked(nid4, nid6);
+  wait_for_graph_.addEdgeUnchecked(nid3, nid5);
+  wait_for_graph_.addEdgeUnchecked(nid6, nid4);
+  wait_for_graph_.addEdgeUnchecked(nid3, nid6);
+  wait_for_graph_.addEdgeUnchecked(nid4, nid6);
 
   // Check whether the edges are already there.
-  EXPECT_TRUE(wait_for_graph.hasEdge(nid3, nid5));
-  EXPECT_TRUE(wait_for_graph.hasEdge(nid6, nid4));
-  EXPECT_TRUE(wait_for_graph.hasEdge(nid4, nid6));
-  EXPECT_TRUE(wait_for_graph.hasEdge(nid3, nid6));
+  EXPECT_TRUE(wait_for_graph_.hasEdge(nid3, nid5));
+  EXPECT_TRUE(wait_for_graph_.hasEdge(nid6, nid4));
+  EXPECT_TRUE(wait_for_graph_.hasEdge(nid4, nid6));
+  EXPECT_TRUE(wait_for_graph_.hasEdge(nid3, nid6));
 
   // Check non-existent edges.
-  EXPECT_FALSE(wait_for_graph.hasEdge(nid5, nid3));
-  EXPECT_FALSE(wait_for_graph.hasEdge(nid6, nid3));
-  EXPECT_FALSE(wait_for_graph.hasEdge(nid4, nid5));
+  EXPECT_FALSE(wait_for_graph_.hasEdge(nid5, nid3));
+  EXPECT_FALSE(wait_for_graph_.hasEdge(nid6, nid3));
+  EXPECT_FALSE(wait_for_graph_.hasEdge(nid4, nid5));
 }
 
-TEST(DirectedGraphTest, GetAdjacentNodes) {
-  // Prepare the graph.
-  DirectedGraph wait_for_graph;
-  transaction_id *tid3 = new transaction_id(3);
-  transaction_id *tid4 = new transaction_id(4);
-  transaction_id *tid5 = new transaction_id(5);
-  transaction_id *tid6 = new transaction_id(6);
-
+TEST_F(DirectedGraphTest, GetAdjacentNodes) {
   // Add 4 disconnected nodes to the graph.
-  DirectedGraph::node_id nid3 = wait_for_graph.addNodeUnchecked(tid3);
-  DirectedGraph::node_id nid6 = wait_for_graph.addNodeUnchecked(tid6);
-  DirectedGraph::node_id nid4 = wait_for_graph.addNodeUnchecked(tid4);
-  DirectedGraph::node_id nid5 = wait_for_graph.addNodeUnchecked(tid5);
+  DirectedGraph::node_id nid3 = wait_for_graph_.addNodeUnchecked(tid3_);
+  DirectedGraph::node_id nid6 = wait_for_graph_.addNodeUnchecked(tid6_);
+  DirectedGraph::node_id nid4 = wait_for_graph_.addNodeUnchecked(tid4_);
+  DirectedGraph::node_id nid5 = wait_for_graph_.addNodeUnchecked(tid5_);
 
-  std::vector<DirectedGraph::node_id> result1 = wait_for_graph.getAdjacentNodes(nid3);
+  std::vector<DirectedGraph::node_id> result1 = wait_for_graph_.getAdjacentNodes(nid3);
   // nid3 has no edge to other nodes.
   EXPECT_EQ(0u, result1.size());
 
   // Now nid3 has outgoing edge to nid4 and nid5.
-  wait_for_graph.addEdgeUnchecked(nid3, nid4);
-  wait_for_graph.addEdgeUnchecked(nid3, nid5);
+  wait_for_graph_.addEdgeUnchecked(nid3, nid4);
+  wait_for_graph_.addEdgeUnchecked(nid3, nid5);
 
-  std::vector<DirectedGraph::node_id> result2 = wait_for_graph.getAdjacentNodes(nid3);
+  std::vector<DirectedGraph::node_id> result2 = wait_for_graph_.getAdjacentNodes(nid3);
   // Therefore, number of outgoing edges from nid3 is 2.
   EXPECT_EQ(2u, result2.size());
 
   // Add an edge from nid3 to nid6.
-  wait_for_graph.addEdgeUnchecked(nid3, nid6);
-  std::vector<DirectedGraph::node_id> result3 = wait_for_graph.getAdjacentNodes(nid3);
+  wait_for_graph_.addEdgeUnchecked(nid3, nid6);
+  std::vector<DirectedGraph::node_id> result3 = wait_for_graph_.getAdjacentNodes(nid3);
 
   // Now there are 3 outgoing edges.
   EXPECT_EQ(3u, result3.size());
 
   // Again add edge from nid3 to nid6.
-  wait_for_graph.addEdgeUnchecked(nid3, nid6);
-  std::vector<DirectedGraph::node_id> result4 = wait_for_graph.getAdjacentNodes(nid3);
+  wait_for_graph_.addEdgeUnchecked(nid3, nid6);
+  std::vector<DirectedGraph::node_id> result4 = wait_for_graph_.getAdjacentNodes(nid3);
   // Since we have already add same edge before, number of edges are still 3.
   EXPECT_EQ(3u, result4.size());
 }

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/tests/LockRequest_unittest.cpp
----------------------------------------------------------------------
diff --git a/transaction/tests/LockRequest_unittest.cpp b/transaction/tests/LockRequest_unittest.cpp
index 0e4138a..77047d9 100644
--- a/transaction/tests/LockRequest_unittest.cpp
+++ b/transaction/tests/LockRequest_unittest.cpp
@@ -31,7 +31,7 @@ class LockRequestTest : public ::testing::Test {
   LockRequestTest()
       : lock_request_(transaction_id(3),
                       ResourceId(5),
-                      AccessMode(AccessModeType::kSLock),
+                      AccessMode::SLockMode(),
                       RequestType::kAcquireLock) {
   }
 
@@ -41,7 +41,7 @@ class LockRequestTest : public ::testing::Test {
 TEST_F(LockRequestTest, CheckGetters) {
   EXPECT_EQ(transaction_id(3), lock_request_.getTransactionId());
   EXPECT_EQ(ResourceId(5), lock_request_.getResourceId());
-  EXPECT_EQ(AccessMode(AccessModeType::kSLock), lock_request_.getAccessMode());
+  EXPECT_EQ(AccessMode::SLockMode(), lock_request_.getAccessMode());
   EXPECT_EQ(RequestType::kAcquireLock, lock_request_.getRequestType());
 }
 

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/tests/LockTable_unittest.cpp
----------------------------------------------------------------------
diff --git a/transaction/tests/LockTable_unittest.cpp b/transaction/tests/LockTable_unittest.cpp
index 577cb79..1aed0b8 100644
--- a/transaction/tests/LockTable_unittest.cpp
+++ b/transaction/tests/LockTable_unittest.cpp
@@ -41,64 +41,73 @@ class LockTableTest : public ::testing::Test {
 };
 
 TEST_F(LockTableTest, CompatibleRequestsFromDifferentTransactions) {
-  EXPECT_EQ(lock_table_.putLock(tid_1_,
+  const AccessMode is_lock_mode = AccessMode::IsLockMode();
+  const AccessMode s_lock_mode = AccessMode::SLockMode();
+
+  EXPECT_EQ(LockTableResult::kPlacedInOwned,
+            lock_table_.putLock(tid_1_,
                                 ResourceId(2),
-                                AccessMode(AccessModeType::kIsLock)),
-            LockTableResult::kPLACED_IN_OWNED);
+                                is_lock_mode));
 
   // Acquire the same lock mode on same resource.
-  EXPECT_EQ(lock_table_.putLock(tid_1_,
+  EXPECT_EQ(LockTableResult::kAlreadyInOwned,
+            lock_table_.putLock(tid_1_,
                                 ResourceId(2),
-                                AccessMode(AccessModeType::kIsLock)),
-            LockTableResult::kALREADY_IN_OWNED);
+                                is_lock_mode));
 
   // Another transaction acquires compatible lock on the same resource.
-  EXPECT_EQ(lock_table_.putLock(tid_2_,
+  EXPECT_EQ(LockTableResult::kPlacedInOwned,
+            lock_table_.putLock(tid_2_,
                                 ResourceId(2),
-                                AccessMode(AccessModeType::kSLock)),
-            LockTableResult::kPLACED_IN_OWNED);
+                                s_lock_mode));
 }
 
 TEST_F(LockTableTest, IncompatibleRequestsFromDifferentTransactions) {
-  EXPECT_EQ(lock_table_.putLock(tid_1_,
+  const AccessMode is_lock_mode = AccessMode::IsLockMode();
+  const AccessMode x_lock_mode = AccessMode::XLockMode();
+
+  EXPECT_EQ(LockTableResult::kPlacedInOwned,
+            lock_table_.putLock(tid_1_,
                                 ResourceId(2),
-                                AccessMode(AccessModeType::kIsLock)),
-            LockTableResult::kPLACED_IN_OWNED);
+                                is_lock_mode));
 
   // Acquire the same lock mode on same resource.
-  EXPECT_EQ(lock_table_.putLock(tid_1_,
+  EXPECT_EQ(LockTableResult::kAlreadyInOwned,
+            lock_table_.putLock(tid_1_,
                                 ResourceId(2),
-                                AccessMode(AccessModeType::kIsLock)),
-            LockTableResult::kALREADY_IN_OWNED);
+                                is_lock_mode));
 
   // Another transaction acquires incompatible lock on the same resource.
-  EXPECT_EQ(lock_table_.putLock(tid_2_,
+  EXPECT_EQ(LockTableResult::kPlacedInPending,
+            lock_table_.putLock(tid_2_,
                                 ResourceId(2),
-                                AccessMode(AccessModeType::kXLock)),
-            LockTableResult::kPLACED_IN_PENDING);
+                                x_lock_mode));
 }
 
 TEST_F(LockTableTest, StarvationProtection) {
-  EXPECT_EQ(lock_table_.putLock(tid_1_,
+  const AccessMode is_lock_mode = AccessMode::IsLockMode();
+  const AccessMode x_lock_mode = AccessMode::XLockMode();
+
+  EXPECT_EQ(LockTableResult::kPlacedInOwned,
+            lock_table_.putLock(tid_1_,
                                 ResourceId(2),
-                                AccessMode(AccessModeType::kIsLock)),
-            LockTableResult::kPLACED_IN_OWNED);
+                                is_lock_mode));
 
   // Another transaction requests incompatible lock on the same resource.
   // It should wait for the previous transaction.
-  EXPECT_EQ(lock_table_.putLock(tid_2_,
+  EXPECT_EQ(LockTableResult::kPlacedInPending,
+            lock_table_.putLock(tid_2_,
                                 ResourceId(2),
-                                AccessMode(AccessModeType::kXLock)),
-            LockTableResult::kPLACED_IN_PENDING);
+                                x_lock_mode));
 
   // Another third transaction requests a compatible lock on the same resource.
   // Normally, it should acquire the lock, however, there is a pending
   // transaction waiting on the same resource. To prevent starvation, we should
   // put in the pending list.
-  EXPECT_EQ(lock_table_.putLock(tid_3_,
+  EXPECT_EQ(LockTableResult::kPlacedInPending,
+            lock_table_.putLock(tid_3_,
                                 ResourceId(2),
-                                AccessMode(AccessModeType::kIsLock)),
-            LockTableResult::kPLACED_IN_PENDING);
+                                is_lock_mode));
 }
 
 }  // namespace transaction

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/bbaff7a2/transaction/tests/Lock_unittest.cpp
----------------------------------------------------------------------
diff --git a/transaction/tests/Lock_unittest.cpp b/transaction/tests/Lock_unittest.cpp
index 2ab8b3e..59a5e7a 100644
--- a/transaction/tests/Lock_unittest.cpp
+++ b/transaction/tests/Lock_unittest.cpp
@@ -18,6 +18,7 @@
 #include "transaction/Lock.hpp"
 
 #include <cstddef>
+#include <memory>
 #include <vector>
 
 #include "transaction/AccessMode.hpp"
@@ -31,12 +32,12 @@ namespace transaction {
 class LockTest : public ::testing::Test {
  protected:
   LockTest()
-      : modes_({AccessMode(AccessModeType::kNoLock),
-                AccessMode(AccessModeType::kIsLock),
-                AccessMode(AccessModeType::kIxLock),
-                AccessMode(AccessModeType::kSLock),
-                AccessMode(AccessModeType::kSixLock),
-                AccessMode(AccessModeType::kXLock)}),
+      : modes_({AccessMode::NoLockMode(),
+                AccessMode::IsLockMode(),
+                AccessMode::IxLockMode(),
+                AccessMode::SLockMode(),
+                AccessMode::SixLockMode(),
+                AccessMode::XLockMode()}),
         resource_a_(3, 10, 2, 5),
         resource_b_(4, 5, 3, 2),
         locks_on_resource_a_({Lock(resource_a_, modes_[0]),



Mime
View raw message