transaction/DeadLockDetector.cpp

/**
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you 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